Un terreno está formado por \(n\) columnas de ancho \(1\) y alturas \(h_0, \dots, h_{n-1}\). Después de llover, ¿cuántas unidades de agua quedan atrapadas entre las columnas?

Entrada

La primera línea tiene \(n\) \((1 \le n \le 10^5)\) y la segunda las alturas \((0 \le h_i \le 10^5)\).

Salida

La cantidad de agua atrapada. (Puede no caber en 32 bits.)

Ejemplo 1

Entrada

12
0 1 0 2 1 0 1 3 2 1 2 1

Salida

6

Ejemplo 2

Entrada

6
4 2 0 3 2 5

Salida

9

Basado en el problema 42 de LeetCode, Trapping Rain Water, adaptado a entrada y salida estándar; enunciado redactado para este juez. Es parte de la lista Grind 75 de Yangshun Tay.