小Wは小Pからキャンディの画像を受け取り、それが非常に素晴らしいと感じたため、お返しとしてあまり素晴らしくない彩り豊かなリボンを贈ることにしました。
小Wはリボンに明暗をつけ、より美しくしようとしています。
$m$ 個のマスからなるリボンに対し、リボンを長さ $m$ の明暗シーケンス $a$ に染めるための染色難易度 $f(a)$ を次のように定義します。
- 初期状態では、リボンの各マスの暗度はすべて $0$ です。
あなたは以下の操作を何度でも行うことができます。
- 任意の2つのマスの間の境界線を折り目としてリボンを折ります。折り畳み操作は複数回行うことも、全く行わないことも可能です。
- 任意の位置に黒い染料を垂らします。染料は上部から浸透して下へ流れ、その経路上のすべてのマスの暗度を $1$ 増加させます。染料を垂らした後、リボンを広げます。
$f(a)$ は、$a_i > 0$ であるすべての位置の暗度が $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}$ で割った余りを出力してください。
入力
1行目に正整数 $n$ が与えられます。
続く1行に、$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 \le 15$ |
| 6 | 5 | $n \le 15$ |
| 7 | 5 | $n \le 500$ |
| 8 | 5 | $n \le 500$ |
| 9 | 5 | $n \le 500$ |
| 10 | 5 | $n \le 500$ |
| 11 | 5 | $n \le 5000$ |
| 12 | 5 | $n \le 5000$ |
| 13 | 5 | $n \le 5000$ |
| 14 | 5 | $n \le 5000$ |
| 15 | 5 | $n \le 50000$ |
| 16 | 5 | $n \le 50000$ |
| 17 | 5 | なし |
| 18 | 5 | なし |
| 19 | 5 | なし |
| 20 | 5 | なし |
すべてのデータについて：$1 \le n \le 10^6, 0 \le b_i \le 10^9$。