题目描述

小 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}$ 取模后的结果。

3
1 0 2

9

6
2 0 1 3 0 1

51

15
8 0 1 9 3 0 0 4 2 6 0 5 7 0 6

993

提示

数据范围

测试点编号	分值	额外限制
1	5	$b_i>0$
2
3		$b_i>0$ 的数量不超过 $300$
4
5		$n\leq15$
6
7		$n\leq500$
8
9
10
11		$n\leq5000$
12
13
14
15		$n\leq50000$
16
17		无
18
19
20

对于所有数据：$1 \le n\le 10^6, 0\le b_i \le 10 ^ 9$。