M. 选择排序
时间限制：每个测试点 2 秒
内存限制：每个测试点 1024 MB

---

题目描述

选算法课的学生这周都要提交一份作业。任务是实现一个时间复杂度为 $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 的代码，但不想直接抄袭。而是想用她的排序函数作为自己方案的基础模块。
你可以用以下两种方式利用她的函数，每种操作最多使用一次，且两种操作的调用顺序任意：

• 前缀排序：选择一个长度 $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 的函数将输入的数组 $s$（包含 $n$ 个整数）排序成非递减顺序，并找出最小的总开销。

---

举例

例 1
输入：$s = [3, 2, 5, 5, 4, 1]$

操作步骤：

1. 先做一次长度为 $4$ 的后缀排序，数组变为 $[3, 2, 1, 4, 5, 5]$
2. 再做一次长度为 $3$ 的前缀排序，数组变为 $[1, 2, 3, 4, 5, 5]$

总开销：$4^2 + 3^2 = 16 + 9 = 25$

例 2
输入：$s = [4, 3, 2, 1]$

操作步骤：
只做一次长度为 $4$ 的前缀排序即可。
总开销：$4^2 = 16$

---

输入格式

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

数据范围：

• $1 \le n \le 10^6$
• $0 \le s_i < 2^{31} - 1$

---

输出格式

输出一个整数，表示将输入数组 $s$ 排成非递减顺序的最小总开销。

---

示例

样例 1
输入：

6
3 2 5 5 4 1

输出：

25

样例 2
输入：

4
4 3 2 1

输出：

16