给定一个长度为 $N$ 的整数数组 $a_1, a_2, \dots, a_N$ ($2 \le N \le 10^6, 1 \le a_i \le N$)。对于 $a$ 的所有 $N(N+1)/2$ 个连续子数组，求出每个子数组对应问题的答案之和。对于给定的非空整数列表，交替执行以下操作（从第一个操作开始），直到列表大小变为 1：将列表中两个相邻的整数替换为它们的最小值；将列表中两个相邻的整数替换为它们的最大值。确定最终剩余整数的最大可能值。例如，$[4, 10, 3] \to [4, 3] \to [4]$；$[3, 4, 10] \to [3, 10] \to [10]$。在第一个数组中，$(10, 3)$ 被替换为 $\min(10, 3)=3$，$(4, 3)$ 被替换为 $\max(4, 3)=4$。

输入格式

第一行包含一个整数 $N$。 第二行包含 $a_1, a_2, \dots, a_N$。

输出格式

所有子数组对应问题的答案之和。

样例

样例输入 1

2
2 1

样例输出 1

4

样例输入 2

3
3 1 3

样例输出 2

12

样例输入 3

4
2 4 1 3

样例输出 3

22

说明

考虑子数组 $[2, 4, 1, 3]$。对 $(1, 3)$ 执行第一个操作，得到新数组 $[2, 4, 1]$。对 $(4, 1)$ 执行第二个操作，得到新数组 $[2, 4]$。对 $(2, 4)$ 执行第三个操作，最终数字为 $2$。可以证明 $2$ 是最终数字的最大可能值。

数据范围

• 输入 4-5：$N \le 100$
• 输入 6-7：$N \le 5000$
• 输入 8-9：$\max(a) \le 10$
• 输入 10-13：无额外限制。