题目描述

有一个长度为 $n$ 的整数序列 $a_1,a_2,...,a_n$，初始时所有数字均为红色。

你可以执行以下两种操作，且每种操作只能执行至多一次：

$∙$ 选择一个位置 $i$，花费 $a_i \times i$ 的代价，把 $a_1,a_2,...,a_i$ 全部染成绿色。

$∙$ 选择一个位置 $i$，花费 $a_i \times (n -i + 1)$ 的代价，把 $a_i,a_{i+1},...,a_n$ 全部染成绿色。

操作完毕后，所有红色的数字均不能相同。

请你求出满足条件所需要的最小操作代价。

输入格式

第一行两个正整数 $n$，表示序列中的元素个数。

第二行 $n$ 个正整数 $a_1,a_2,...,a_n$ 表示序列中的每个元素。

输出格式

一个整数，表示答案。

5
1 2 3 2 1

4

5
1 2 3 4 5

0

样例解释

对于第一组样例，一个合理的方式是将 $a_1,a_2$ 都染成绿色，代价为 $2 \times 2 = 4$。

容易证明没有比这更小的代价。

如图所示：

数据规模与约定

下发文件

下发文件分别对应子任务 $1$、$4$。

有合理的子任务依赖。

对于 $100\%$ 的数据：保证 $1 \leq n \leq 3 \times 10^{5},1 \leq a_i \leq 10^{9}$。