Vous souhaitez vous entraîner au patinage sur un parcours donné. Ce parcours comprend un point de départ, $N$ points intermédiaires et un point d’arrivée. L’entraînement commence au départ à une vitesse de $0$, passe par les points intermédiaires de $1$ à $N$ dans l’ordre croissant de leurs numéros, et se termine après avoir atteint l’arrivée à une vitesse de $0$.

Chaque point intermédiaire possède une limite de vitesse $V_i$ ; vous devez donc ajuster votre vitesse pendant le déplacement pour ne pas dépasser la limite du prochain point visité. Vous pouvez augmenter votre vitesse autant que vous le souhaitez, mais lorsque vous ralentissez, vous ne pouvez la diminuer que de $1$ par rapport à la vitesse au dernier point visité. La vitesse ne peut être $0$ ailleurs qu’au départ et à l’arrivée. Vous pouvez aussi conserver une vitesse inchangée.

Le résultat de l’entraînement est la somme des vitesses à tous les points, et vous souhaitez le maximiser. Étant données les limites de vitesse du parcours, trouvez le meilleur résultat d’entraînement que vous pouvez y obtenir.

Par exemple, considérons un parcours de trois points intermédiaires avec les limites $V=[2,3,1]$. Si vous conservez une vitesse de $3$ au point intermédiaire $2$, il est impossible de la ramener à au plus $1$ au point intermédiaire $3$. Un entraînement possible utilise les vitesses $[2,2,1]$, de somme $2+2+1=5$. D’autres entraînements possibles sont $[1,1,1]$ et $[1,2,1]$, mais leurs sommes ne dépassent pas $5$. Le meilleur résultat possible sur ce parcours est donc $5$.

Contraintes

• Tous les nombres donnés sont entiers.
• $1 \le N \le 500000$
• $1 \le V_i \le 1000000000$ ($1 \le i \le N$)

Sous-tâches

1. 8 points: $N \le 8$, $V_i \le 8$ ($1 \le i \le N$)
2. 12 points: $N \le 500$, $V_i \le 500$ ($1 \le i \le N$)
3. 17 points: $N \le 5000$, $V_i \le 5000$ ($1 \le i \le N$)
4. 10 points: $N \le 5000$
5. 53 points: Aucune contrainte supplémentaire.

Entrée

La première ligne contient $N$.

La deuxième ligne contient $V_1,V_2,\ldots,V_N$, dans cet ordre, séparés par des espaces.

Sortie

Affichez la réponse sur la première ligne.

Exemples

Entrée 1

3
2 3 1

Sortie 1

5

Entrée 2

4
23 7 1 5

Sortie 2

7