【题目描述】

Bessie 喜欢在她的手机上下载游戏玩，尽管她确实发现对于她的大蹄子来说使用小触摸屏相当麻烦。

她对目前正在玩的游戏特别着迷。游戏从 N 个 1…10^6 范围内的正整数组成的序列 a1,a2,…,aN（2≤N≤262,144）开始。在一次行动中，Bessie 可以取两个相邻的数字并将它们替换为一个大于两数最大值的数字（例如，她可以将相邻的一对数 (5,7) 替换为 8）。游戏在 N−1 次行动后结束，此时只剩下一个数字。游戏目标是最小化这个最终的数字。

Bessie 知道这个游戏对你来说太容易了。所以你的任务不仅仅是在 a 上以最优方式玩游戏，而是在 a 的每个连续子段上玩游戏。

输出 a 的所有 N(N+1)/2 个连续子段的最小最终数字之和。

【输入格式】（从终端 / 标准输入读入）：

输入的第一行包含 N。

第二行包含 N 个空格分隔的整数，表示输入的序列。

【输出格式】（输出至终端 / 标准输出）：

输出一行，包含所求的和。

【输入样例】：

6

1 3 1 2 1 10

【输出样例】：

115

共有 6×7/2=21个连续子段。例如，连续子段 [1,3,1,2,1] 的最小可能的最终数字是 5，可以通过以下操作序列达到：

初始     -> [1,3,1,2,1]

合并 1&3 -> [4,1,2,1]

合并 2&1 -> [4,1,3]

合并 1&3 -> [4,4]

合并 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≤300。

测试点 4-5 满足 N≤3000。

测试点 6-8 中，输入的序列中所有数的值不超过 40。

测试点 9-11 中，输入的序列是不下降的。

测试点 12-23 没有额外限制。