Hay \(n\) niños en fila y cada uno tiene una calificación \(r_i\). Hay que repartirles dulces cumpliendo:

• cada niño recibe al menos un dulce;
• un niño con calificación mayor que la de un vecino recibe más dulces que ese vecino.

Encuentra la menor cantidad total de dulces.

Entrada

La primera línea tiene \(n\) \((1 \le n \le 10^5)\). La segunda tiene las \(n\) calificaciones, entre \(0\) y \(2 \cdot 10^4\).

Salida

La menor cantidad total de dulces.

Ejemplo 1

Entrada

3
1 0 2

Salida

5

Ejemplo 2

Entrada

3
1 2 2

Salida

4

Ejemplo 3

Entrada

1
5

Salida

1