题目描述

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

1. 选择一个下标i，花费$a_i \times i$的代价，将这个位置及之前的所有元素都染成红色；
2. 选择一个下标i，花费$a_i \times (n-i+1)$的代价，将这个位置及之后的所有元素都染成红色；

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

输入格式

第一行输入一个整数$n$，代表数组大小, $1<=n<=3e5$

第二行输入$n$个整数，代表数组内的元素$a_1,a_2....a_n$，$1<=a[i]<=1e9$。

输出格式

一个数，代表最小代价。

5
1 2 3 2 1

4