每个注册算法课程的学生都必须在本周提交作业。任务是实现 $$$O(n^2)$$$ 时间算法,以非降序对给定整数 $$$n$$$ 进行排序。 Alice 已经完成了她的任务,她的实现如下所示。
虽然您可以访问 Alice 的代码,但您不希望简单地复制它。相反,您希望使用 Alice 的排序函数作为您自己的解决方案的构建块。您可以通过下面列出的两种方式来利用她的功能,但每种方式最多只能应用一次。这两个操作的调用顺序可以是任意的。
- 前缀排序:选择长度 $$$i \in \{1, 2, \ldots, n\}$$$ 并调用 $$$\texttt{alicesort(}s, i\texttt{)}$$$。这对数组 $$$s$$$ 中的前 $$$i$$$ 元素进行排序。
- 后缀排序:选择长度 $$$i \in \{1, 2, \ldots, n\}$$$ 并调用 $$$\texttt{alicesort(}s+n-i, i\texttt{)}$$$。这对数组 $$$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$$$ 中整数的数量。第二行包含 $$$s=[s_0, s_1, \ldots, s_{n-1}]$$$ 中的 $$$n$$$ 整数。
- $$$1 \le n \le 10^6$$$
- 对于所有 $$$i$$$ ($$$0\le i < n$$$),$$$0\le s_i < 2^{31}-1$$$。
输出
在一行上输出一个整数,表示按照上述规则,使用 Alice 函数对输入数组 $$$s$$$ 的 $$$n$$$ 个整数进行非降序排序的最小成本。
示例
输入 #1
6 3 2 5 5 4 1
输出 #1
25
输入 #2
4 4 3 2 1
输出 #2
16