Pretende praticar patinagem num percurso dado. O percurso consiste num ponto de partida, $N$ pontos intermédios e um ponto de chegada. O treino começa na partida com velocidade $0$, visita os pontos intermédios de $1$ a $N$ por ordem crescente do número e termina após alcançar a chegada com velocidade $0$.

Cada ponto intermédio tem um limite de velocidade $V_i$, pelo que deve ajustar a velocidade durante o deslocamento para não exceder o limite do próximo ponto a visitar. Pode aumentar a velocidade tanto quanto quiser, mas, ao abrandar, apenas a pode reduzir em $1$ relativamente à velocidade no último ponto visitado. A velocidade não pode ser $0$ em nenhum local exceto na partida e na chegada. Também pode manter a velocidade inalterada.

O resultado do treino é a soma das velocidades em todos os pontos, e pretende maximizá-lo. Dados os limites de velocidade do percurso, determine o maior resultado de treino que pode obter nesse percurso.

Por exemplo, suponha que existem três pontos intermédios com limites $V=[2,3,1]$. Se mantiver a velocidade $3$ no ponto intermédio $2$, será impossível ajustá-la para no máximo $1$ no ponto intermédio $3$. Um treino possível usa as velocidades $[2,2,1]$, cuja soma é $2+2+1=5$. Outros treinos possíveis são $[1,1,1]$ e $[1,2,1]$, mas as suas somas não excedem $5$. Assim, o maior resultado possível neste percurso é $5$.

Restrições

• Todos os números dados são inteiros.
• $1 \le N \le 500000$
• $1 \le V_i \le 1000000000$ ($1 \le i \le N$)

Subtarefas

1. 8 pontos: $N \le 8$, $V_i \le 8$ ($1 \le i \le N$)
2. 12 pontos: $N \le 500$, $V_i \le 500$ ($1 \le i \le N$)
3. 17 pontos: $N \le 5000$, $V_i \le 5000$ ($1 \le i \le N$)
4. 10 pontos: $N \le 5000$
5. 53 pontos: Sem restrições adicionais.

Entrada

A primeira linha contém $N$.

A segunda linha contém $V_1,V_2,\ldots,V_N$, por esta ordem, separados por espaços.

Saída

Imprima a resposta na primeira linha.

Exemplos

Entrada 1

3
2 3 1

Saída 1

5

Entrada 2

4
23 7 1 5

Saída 2

7