问题描述

在古老的魔法学院中，魔导师们发现了一种蕴含巨大能量的神秘晶体。这种晶体极其不稳定，必须通过特定的分裂才能安全地释放其中蕴含的能量。

一块完整的能量晶体由 $n$ 个能量单元依次排列组成。我们用一个长度为 $n$ 的数组 $A$ 来表示每个能量单元的能量系数，其中 $A_i$ 表示第 $i$ 个单元的能量系数。

能量晶体的分裂遵循折半法则：对于一块下标范围在 $[L, R]$ 的能量晶体，若其长度大于 $1$，它将从中间分裂为两块较小的晶体，分裂点为

$$mid = \left\lfloor \frac{L+R}{2} \right\rfloor. \tag{1}$$

分裂过程会产生一次性的能量释放，释放量的计算公式为

$$E = \left(\max_{i=L}^{mid} A_i\right) \times \left(\min_{j=mid+1}^{R} A_j\right). \tag{2}$$

其中，$\displaystyle\max_{i=L}^{mid} A_i$ 表示左半部分晶体中能量系数最大的单元，$\displaystyle\min_{j=mid+1}^{R} A_j$ 表示右半部分晶体中能量系数最小的单元。分裂后的两块下标范围分别为 $[L,mid]$ 和 $[mid+1,R]$ 的晶体可以继续进行分裂，直到晶体长度为 $1$ 时停止（长度为 $1$ 的晶体不再产生能量）。

计算这块能量晶体在完全分裂过程中累计释放的总能量。

输入格式

第一行包含一个整数 $n$，表示能量单元的数量。

第二行包含 $n$ 个整数 $A_1, A_2, \dots, A_n$，依次表示每个能量单元的能量系数。

输出格式

输出一个整数，表示答案 —— 完全分裂过程中累计释放的总能量。

样例输入 1

4
3 2 4 1

样例输出 1

13

样例解释 1

1. 初始区间 $[1,4]$，由 (1) 得 $mid=2$。 左半区间 $[1,2]$ 的最大值为 $3$，右半区间 $[3,4]$ 的最小值为 $1$，产生能量

   $$E = 3 \times 1 = 3.$$

2. 处理区间 $[1,2]$，$mid=1$。 左半区间 $[1,1]$ 的最大值为 $3$，右半区间 $[2,2]$ 的最小值为 $2$，产生能量

   $$E = 3 \times 2 = 6.$$

3. 处理区间 $[3,4]$，$mid=3$。 左半区间 $[3,3]$ 的最大值为 $4$，右半区间 $[4,4]$ 的最小值为 $1$，产生能量

   $$E = 4 \times 1 = 4.$$

总能量为 $3 + 6 + 4 = 13$。

样例输入 2

10
2 3 1 9 1 7 2 6 2 4

样例输出 2

117

评测数据规模

对于 $100\%$ 的数据，$1 \le n \le 2 \times 10^5$，$0 \le A_i \le 10^6$。

测试点编号	$n \le$	特殊性质
$1 \sim 3$	$10^3$	无
$4 \sim 5$	$2\times 10^5$	A
$6 \sim 7$		B
$8 \sim 10$		无

特殊性质 A：序列 $A$ 中所有元素均相同。

特殊性质 B：$\forall i < n, A_i \le A_{i+1}$，即序列 $A$ 是非递减的。