题目描述

注意：本题的时间限制为 3 秒，通常限制的 1.5 倍。

给定一个长为 $N$ 的整数数组 $a_1,a_2,\dots,a_N$（$2\le N \le 10^6$，$1\le a_i\le N$)。输出所有 $N(N+1)/2$ 个 $a$ 的连续子数组的以下子问题的答案之和。

给定一个非空整数列表，交替执行以下操作（从第一个操作开始）直到列表大小恰好为一。

1. 将列表内的两个相邻整数替换为它们的较小值。
2. 将列表内的两个相邻整数替换为它们的较大值。

求最终余下的整数的最大可能值。

例如，

$[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

输入 #1

2
2 1

输出 #1

4

输入输出样例 #2

输入 #2

3
3 1 3

输出 #2

12

输入输出样例 #3

输入 #3

4
2 4 1 3

输出 #3

22

说明/提示

样例 1 解释：

对于 $[2]$ 答案为 $2$，对于 $[1]$ 答案为 $1$，对于 $[2, 1]$ 答案为 $1$。

因此，我们的输出应当为 $2+1+1 = 4$。

样例 3 解释：

考虑子数组 $[2, 4, 1, 3]$。

1. 在 $(1, 3)$ 上应用第一次操作，我们的新数组是 $[2, 4, 1]$。
2. 在 $(4, 1)$ 上应用第二次操作，我们的新数组是 $[2, 4]$。
3. 在 $(2, 4)$ 上应用第三次操作，我们最终的数是 $2$。

可以证明 $2$ 是最终的数的最大可能值。

• 测试点 $4\sim 5$：$N\le 100$。
• 测试点 $6\sim 7$：$N\le 5000$。
• 测试点 $8\sim 9$：$\max(a)\le 10$。
• 测试点 $10\sim 13$：没有额外限制。