Después de recibir la imagen de la piruleta de Xiao P, Xiao W pensó que era tan genial que decidió devolverle una cinta de colores no tan genial.
Xiao W añade brillo y oscuridad a la cinta de colores para hacerla más hermosa.
Para una cinta de colores compuesta por $m$ celdas, definimos la dificultad de teñido $f(a)$ para obtener una secuencia de brillo y oscuridad $a$ de longitud $m$ como:
Inicialmente, el nivel de oscuridad de cada celda en la cinta es $0$.
Puedes realizar varias operaciones. En cada operación, debes:
- Doblar la cinta usando la línea divisoria entre dos celdas cualesquiera como pliegue. La operación de doblado puede realizarse varias veces o no realizarse en absoluto.
- Elegir una posición para verter tinte negro; el tinte penetrará desde la parte superior y fluirá hacia abajo, aumentando en $1$ el nivel de oscuridad de todas las celdas en su trayectoria. Después de verter el tinte, despliega la cinta.
$f(a)$ representa el número mínimo de operaciones necesarias para que todas las posiciones donde $a_i > 0$ tengan un nivel de oscuridad $\ge a_i$, y todas las posiciones donde $a_i = 0$ tengan un nivel de oscuridad exactamente igual a $0$.
Ahora, Xiao W tiene una cinta de colores de longitud $n$ y una secuencia de brillo y oscuridad alternativa $b$ de longitud $n$. Como aún no ha decidido qué secuencia es la más atractiva, desea que calcules la suma de las dificultades de teñido de todas las subsecciones $[l, r]$ de $b$ para cintas de colores compuestas por $r-l+1$ celdas. Formalmente, necesitas calcular $\sum\limits_{1\le l\le r\le n}f(b[l,r])$.
La respuesta debe imprimirse módulo $2^{64}$.
Entrada
La primera línea contiene un número entero positivo $n$.
La siguiente línea contiene $n$ números enteros no negativos $b_1, b_2, \dots, b_n$.
Salida
Un número entero no negativo que representa el resultado de la respuesta módulo $2^{64}$.
Ejemplos
Entrada 1
3 1 0 2
Salida 1
9
Entrada 2
6 2 0 1 3 0 1
Salida 2
51
Entrada 3
15 8 0 1 9 3 0 0 4 2 6 0 5 7 0 6
Salida 3
993
Restricciones
| Número de caso | Puntuación | Restricciones adicionales |
|---|---|---|
| 1 | 5 | $b_i>0$ |
| 2 | 5 | $b_i>0$ |
| 3 | 5 | La cantidad de $b_i>0$ no supera $300$ |
| 4 | 5 | La cantidad de $b_i>0$ no supera $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 | Ninguna |
| 18 | 5 | Ninguna |
| 19 | 5 | Ninguna |
| 20 | 5 | Ninguna |
Para todos los datos: $1 \le n\le 10^6, 0\le b_i \le 10 ^ 9$.