该比赛已结束，您无法在比赛模式下递交该题目。您可以点击“在题库中打开”以普通模式查看和递交本题。

Description

小H拿到了一个长度为 $n$ 的数组$a_1,a_2,...,a_n$,初始所有数都是黑色,她可以进行以下两种操作,每种操作最多进行一次：

选择一个下标 $i$, 花费 $a_i * i$ 的代价, 将 $a_i$ 和 $a_i$ 之前的所有元素都染成红色;

选择一个下标 $i$, 花费 $a_i * (n - i + 1)$ 的代价, 将 $a_i$ 和 $a_i$ 之后的所有元素都染成红色。

小H希望最终数组不包含任意相同的黑色元素, 请你帮他求出所需的最小代价

Format

Input

第一行输入一个整数$n (1 \leq n \leq 2 * 10^5)$, 代表数组的长度。

第二行输入$n$个整数$a_1, a_2, ... ,a_n(1 \leq a_i \leq 10^9)$,代表其中的元素。

Output

输出最小代价。

Samples

5
1 2 3 2 1

4

选择下标4执行第二种操作,花费2 * 2 = 4的代价, 后两个数字被染红, 所有黑色元素互不相同。

Limitation

1s, 1024KiB for each test case.