P14516 [NFLSPC #8] 小 W，小 P，彩丝带

小 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 | 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 | ^ | ^ | | 16 | ^ | ^ | | 17 | ^ | 无 | | 18 | ^ | ^ | | 19 | ^ | ^ | | 20 | ^ | ^ | 对于所有数据：$1 \le n\le 10^6, 0\le b_i \le 10 ^ 9$。