题目描述

$\red{n\times n}$的矩阵 让你从$\red{(0,0)}$走到$\red{(n,n)}$每次只能向上走或者向右走且步长至少为$\red{1，}$而且走完之后必须 换方向，最多换$\red{n-1}$次方向，也就是走$\red{n}$段路。每段路都有一个权值，第$\red{i}$端路的权值是$\red{c[i]，}$这段 路的计算代价为这次走的长度$\red{×}$这段路的权值$\red{(c[i]) ，}$求从 $\red{(0,0)}$走到$\red{(n,n)}$的最小的代价。

输入格式

第一行一个整数$\red{n，}$表示最多的路的段数。

第二行一行$\red{n}$个整数$\red{c_i，}$表示第$\red{i}$段路的权值。

输出格式

一行一个整数，表示从 $\red{(0,0)}$走到$\red{(n,n)}$的最小的代价。

样例

输入样例

2
13 88

输出样例

202

提示

对于$\red{50\%}$的数据，$\red{1<=n<=10^2}$。

对于$\red{100\%}$的数据，$\red{1<=n<=10^5,1<=c_i<=10^9}$。