本周，所有选修算法课程的学生都需要提交一份作业。任务是实现一个 $O(n^2)$ 时间复杂度的算法，将给定的 $n$ 个整数按非降序排序。Alice 已经完成了她的作业，她的实现如下所示：

int alice_sort(int *s, int n){
    for (int i = 0; i < n; ++i){
        for (int j = i + 1; j < n; ++j){
            if (s[i] > s[j]) {
                int swap = s[i];
                s[i] = s[j];
                s[j] = swap;
            }
        }
    }
    return 0;
}

虽然你可以查看 Alice 的代码，但你不想简单地复制它。相反，你想将 Alice 的排序函数作为你自己解决方案的基石。你可以通过以下两种方式来利用她的函数，但每种方式最多只能使用一次。调用这两个操作的顺序可以是任意的。

• 前缀排序：选择一个长度 $i \in \{1, 2, \dots, n\}$ 并调用 alicesort(s, i)。这将对数组 $s$ 的前 $i$ 个元素进行排序。
• 后缀排序：选择一个长度 $i \in \{1, 2, \dots, n\}$ 并调用 alicesort(s + n - i, i)。这将对数组 $s$ 的后 $i$ 个元素进行排序。

由于该排序算法的时间复杂度，进行前缀或后缀排序的代价为 $i^2$，其中 $i$ 是所选子数组的长度。你的目标是在遵循上述规则的情况下，使用 Alice 的函数将包含 $n$ 个整数的输入数组 $s$ 按非降序排序所需的最小代价。

例如，设 $s = [3, 2, 5, 5, 4, 1]$。我们可以先进行一次长度为 $4$ 的后缀排序，数组变为 $[3, 2, 1, 4, 5, 5]$。然后，我们进行一次长度为 $3$ 的前缀排序，数组变为 $[1, 2, 3, 4, 5, 5]$，这是一个已排序的数组。总代价为 $4^2 + 3^2 = 25$。再比如，设 $s = [4, 3, 2, 1]$。我们可以仅通过进行一次长度为 $4$ 的前缀排序来完成排序，代价为 $4^2 = 16$。

输入格式

第一行包含一个整数 $n$，表示数组 $s$ 中的整数个数。

第二行包含 $n$ 个整数，表示 $s = [s_0, s_1, \dots, s_{n-1}]$。

数据范围

• $1 \le n \le 10^6$
• 对于所有 $i$ ($0 \le i < n$)，$0 \le s_i < 2^{31} - 1$。

输出格式

输出一行一个整数，表示在遵循上述规则的情况下，使用 Alice 的函数将包含 $n$ 个整数的输入数组 $s$ 按非降序排序所需的最小代价。

样例

输入样例 1

6
3 2 5 5 4 1

输出样例 1

25

输入样例 2

4
4 3 2 1

输出样例 2

16