Получив от Сяо П. рисунок леденца, Сяо В. счел его настолько «леденцовым», что в ответ подарил ему не менее «леденцовую» цветную ленту.
Сяо В. решил украсить ленту, добавив на нее узор из света и тени.
Для цветной ленты, состоящей из $m$ ячеек, определим сложность окрашивания $f(a)$ для получения последовательности яркости $a$ длины $m$ следующим образом:
- Изначально яркость каждой ячейки ленты равна $0$.
Вы можете выполнить несколько операций. Каждая операция состоит из следующих шагов:
- Сложить ленту по линии сгиба между любыми двумя ячейками. Операцию складывания можно выполнять любое количество раз (в том числе ноль).
- Выбрать позицию и капнуть черную краску. Краска просачивается сверху вниз, увеличивая яркость всех ячеек на своем пути на $1$. После нанесения краски ленту нужно развернуть.
$f(a)$ — это минимальное количество операций, необходимое для того, чтобы яркость всех ячеек, где $a_i > 0$, стала $\ge a_i$, а яркость всех ячеек, где $a_i = 0$, осталась ровно $0$.
Теперь у Сяо В. есть цветная лента длины $n$ и последовательность яркости $b$ длины $n$. Он еще не решил, какой узор будет выглядеть лучше всего, поэтому просит вас вычислить сумму сложностей окрашивания для всех подпоследовательностей $b$ на отрезках $[l, r]$. Формально, вам нужно найти $\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$.