Après avoir reçu le dessin de sucette de Xiao P, Xiao W a trouvé cela tellement « sucette » qu'il a offert en retour un ruban coloré un peu moins « sucette ».
Xiao W ajoute des nuances de clair et d'obscur sur le ruban coloré pour le rendre plus beau.
Pour un ruban coloré composé de $m$ cases, on définit la difficulté de coloration $f(a)$ pour obtenir une séquence de nuances $a$ de longueur $m$ comme suit :
- Initialement, l'obscurité de chaque case du ruban est de $0$.
- Vous pouvez effectuer plusieurs opérations. À chaque opération, vous devez :
- Plier le ruban en utilisant la ligne de séparation entre deux cases quelconques comme pli. L'opération de pliage peut être effectuée plusieurs fois, ou pas du tout.
- Choisir une position pour déposer de la teinture noire. La teinture pénètre par le haut et s'écoule vers le bas, augmentant de $1$ l'obscurité de toutes les cellules sur son passage. Après avoir déposé la teinture, dépliez le ruban.
- $f(a)$ représente le nombre minimum d'opérations nécessaires pour que, pour toutes les positions où $a_i > 0$, l'obscurité soit $\ge a_i$, et pour toutes les positions où $a_i = 0$, l'obscurité soit exactement $0$.
Xiao W possède un ruban coloré de longueur $n$ et une séquence de nuances alternative $b$ de longueur $n$. Comme il n'a pas encore décidé quelle combinaison de nuances est la plus belle, il souhaite que vous calculiez la somme des difficultés de coloration pour tous les sous-intervalles $[l, r]$ de $b$, en considérant des rubans composés de $r-l+1$ cases. Formellement, vous devez calculer $\sum\limits_{1\le l\le r\le n}f(b[l,r])$.
La réponse doit être donnée modulo $2^{64}$.
Entrée
La première ligne contient un entier positif $n$.
La ligne suivante contient $n$ entiers non négatifs $b_1, b_2, \dots, b_n$.
Sortie
Un entier non négatif représentant le résultat modulo $2^{64}$.
Exemples
Entrée 1
3 1 0 2
Sortie 1
9
Entrée 2
6 2 0 1 3 0 1
Sortie 2
51
Entrée 3
15 8 0 1 9 3 0 0 4 2 6 0 5 7 0 6
Sortie 3
993
Contraintes
| Numéro du test | Score | Contraintes supplémentaires |
|---|---|---|
| 1 | 5 | $b_i>0$ |
| 2 | 5 | $b_i>0$ |
| 3 | 5 | Le nombre de $b_i>0$ ne dépasse pas $300$ |
| 4 | 5 | Le nombre de $b_i>0$ ne dépasse pas $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 | Aucune |
| 18 | 5 | Aucune |
| 19 | 5 | Aucune |
| 20 | 5 | Aucune |
Pour toutes les données : $1 \le n\le 10^6, 0\le b_i \le 10 ^ 9$.