小 W 收到小 P 的棒棒糖的图之后觉得这实在是太棒棒糖了，于是回馈了一条不那么棒棒糖的彩丝带。
小 W 给彩丝带上点明暗，让它更加美丽。
对于一条由 $m$ 个格子组成的彩丝带，定义将彩丝带染成长度为 $m$ 的明暗序列 $a$ 的染色难度 $f(a)$ 为：
- 初始，彩丝带上每个格子暗度均为 $0$。
你可以进行若干次操作，每次操作你需要：
- 以任意两个格子之间的分隔线为折痕折叠丝带，折叠操作可以进行多次，也可以不折叠。
- 选择一个位置滴下黑色染料，染料会从顶部渗透并向下流动，使其路径上所有单元格的暗度增加 $1$。滴完染料后展开丝带。
$f(a)$ 表示最少需要几次操作，才能使得所有 $a_i>0$ 的位置的暗度 $\ge a_i$，且所有 $a_i=0$ 的位置的暗度恰好为 $0$。
现在小 W 有一个长度为 $n$ 的彩丝带与一个长度为 $n$ 的备选明暗序列 $b$。他还没有想好怎样的明暗最好看，于是他希望你对于所有 $b$ 的子区间 $[l,r]$，将 $r-l+1$ 个格子组成的彩丝带染色的难度之和。形式化地讲，你需要求出 $\sum\limits_{1\le l\le r\le n}f(b[l,r])$。
答案对 $2^{64}$ 取模输出。
输入格式
第一行一个正整数 $n$。
接下来一行 $n$ 个非负整数 $b_1, b_2, \dots, b_n$。
输出格式
一个非负整数表示答案对 $2^{64}$ 取模后的结果。
样例输入 1
3 1 0 2
样例输出 1
9
样例输入 2
6 2 0 1 3 0 1
样例输出 2
51
样例输入 3
15 8 0 1 9 3 0 0 4 2 6 0 5 7 0 6
样例输出 3
993
数据范围
| 测试点编号 | 分值 | 额外限制 |
|---|---|---|
| 1 | 5 | $b_i>0$ |
| 2 | 5 | $b_i>0$ |
| 3 | 5 | $b_i>0$ 的数量不超过 $300$ |
| 4 | 5 | $b_i>0$ 的数量不超过 $300$ |
| 5 | 5 | $n\leq15$ |
| 6 | 5 | $n\leq15$ |
| 7 | 5 | $n\leq500$ |
| 8 | 5 | $n\leq500$ |
| 9 | 5 | $n\leq500$ |
| 10 | 5 | $n\leq500$ |
| 11 | 5 | $n\leq5000$ |
| 12 | 5 | $n\leq5000$ |
| 13 | 5 | $n\leq5000$ |
| 14 | 5 | $n\leq5000$ |
| 15 | 5 | $n\leq50000$ |
| 16 | 5 | $n\leq50000$ |
| 17 | 5 | 无 |
| 18 | 5 | 无 |
| 19 | 5 | 无 |
| 20 | 5 | 无 |
对于所有数据：$1 \le n\le 10^6, 0\le b_i \le 10 ^ 9$。