Camila es la encargada de la decoración del escenario en un importante evento de charlas de programación 404 Fest.

A lo largo del escenario hay \(N\) soportes alineados en fila, numerados del 1 al \(N\).

El soporte \(i\) tiene una altura \(H_i\).

Para adornar, Camila planea colocar globos entre soportes con la siguiente regla estricta:

• Cada soporte \(i\) intenta tender una fila de globos hacia la izquierda y otra hacia la derecha.
• Una fila de globos solo puede atarse desde el soporte \(i\) hasta el primer soporte en esa dirección cuya altura sea estrictamente mayor que la de \(i\) (es decir, \(H_j > H_i\)).
• Si no existe tal soporte en esa dirección, esa fila no se coloca y no cuenta.

La cantidad de globos de una fila es igual al número de espacios entre los dos soportes. Por ejemplo, si el soporte se conecta con su vecino inmediato, la fila lleva 1 globo; si hay 3 espacios en medio, lleva 3 globos.

Camila necesita calcular cuántos globos en total debe comprar para completar la decoración.

• Línea 1: un entero \(N\) \((1 \le N \le 5 \cdot 10^5)\).
• Línea 2: \(N\) enteros \(H_1, H_2, \ldots, H_N\) \((1 \le H_i \le 10^9)\).

• Un entero: la cantidad total de globos que se colocarán.

Ejemplo 1

Ejemplo 2

Ejemplo 3