小 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$。