Bessie 喜欢在手机上下载游戏，尽管她发现用她那巨大的蹄子操作小小的触摸屏相当笨拙。

她对目前正在玩的游戏非常感兴趣。游戏开始时有一个包含 $N$ 个正整数的序列 $a_1, a_2, \ldots, a_N$ ($2 \le N \le 262,144$)，每个数都在 $1 \ldots 10^6$ 的范围内。在一次操作中，Bessie 可以选取两个相邻的数字，并将它们替换为一个等于这两个数中较大值加 $1$ 的新数字（例如，她可以将相邻的一对 $(5, 7)$ 替换为 $8$）。游戏在进行 $N-1$ 次操作后结束，此时只剩下一个数字。目标是使这个最终数字最小化。

Bessie 知道这个游戏对你来说太简单了。所以你的任务不仅是在序列 $a$ 上以最优方式进行游戏，而是要对 $a$ 的每一个连续子序列都进行计算。

输出所有 $\frac{N(N+1)}{2}$ 个连续子序列的最小可能最终数字之和。

输入格式

第一行包含 $N$。

下一行包含 $N$ 个用空格分隔的整数，表示输入序列。

输出格式

输出一个整数，表示总和。

样例

样例输入 1

6
1 3 1 2 1 10

样例输出 1

115

说明

总共有 $\frac{6 \cdot 7}{2} = 21$ 个连续子序列。例如，连续子序列 $[1, 3, 1, 2, 1]$ 的最小可能最终数字是 $5$，可以通过以下操作序列获得：

original    -> [1,3,1,2,1]
combine 1&3 -> [4,1,2,1]
combine 2&1 -> [4,1,3]
combine 1&3 -> [4,4]
combine 4&4 -> [5]

以下是每个连续子序列的最小可能最终数字：

final(1:1) = 1
final(1:2) = 4
final(1:3) = 5
final(1:4) = 5
final(1:5) = 5
final(1:6) = 11
final(2:2) = 3
final(2:3) = 4
final(2:4) = 4
final(2:5) = 5
final(2:6) = 11
final(3:3) = 1
final(3:4) = 3
final(3:5) = 4
final(3:6) = 11
final(4:4) = 2
final(4:5) = 3
final(4:6) = 11
final(5:5) = 1
final(5:6) = 11
final(6:6) = 10

子任务

• 测试点 2-3 满足 $N \le 300$。
• 测试点 4-5 满足 $N \le 3000$。
• 测试点 6-8 中，所有数值最大为 $40$。
• 测试点 9-11 中，输入序列是非递减的。
• 测试点 12-23 没有额外限制。

题目来源：Benjamin Qi