小红的数组操作
时间限制：C/C++/Rust/Pascal 1秒，其他语言2秒
空间限制：C/C++/Rust/Pascal 1024 M，其他语言2048 M
64bit IO Format: %lld

题目描述

\hspace{15pt}小红拿到了一个长度为 n 的数组 a_1,a_2,\dots,a_n，初始所有数组都是黑色，她可以进行以下两种操作，每种操作最多进行一次：
\hspace{23pt}\bullet\,选择一个下标 i，花费 a_i \times i 的代价，将 a_i 和 a_i 之前的所有元素都染成红色；
\hspace{23pt}\bullet\,选择一个下标 i，花费 a_i \times (n - i + 1) 的代价，将 a_i 和 a_i 之后的所有元素都染成红色。
\hspace{15pt}小红希望最终数组不包含任意相同的黑色元素，请你帮小红求出所需要的最小代价。

输入描述:

\hspace{15pt}第一行输入一个整数 n \left(1\leqq n \leqq 3 \times 10^5\right)，代表数组的大小。
\hspace{15pt}第二行输入 n 个整数 a_1,a_2,\dots,a_n \left(1\leqq a_i \leqq 10^9\right)，代表数组的元素。

输出描述:

\hspace{15pt}输出一个整数，代表小红所需要的最小代价。
示例1

输入

复制 
5
1 2 3 2 1

输出

复制 
4

说明

\hspace{15pt}在这个样例中，其中一种合法的操作方法是：选择下标 4 执行第二种操作，花费 2 \times 2 = 4 的代价，后两个数字被染红，数组为 \{1,2,3,{\color{red}{2}},{\color{red}{1}}\}，所有黑色元素互不相同。