Hay \(n\) paredes verticales en las posiciones \(0, 1, \dots, n-1\); la pared \(i\) tiene altura \(h_i\). Elige dos paredes \(i < j\): junto con el suelo forman un recipiente que guarda \(\min(h_i, h_j) \cdot (j - i)\) unidades de agua. Calcula el máximo posible.

Entrada

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

Salida

La máxima cantidad de agua.

Ejemplo 1

Entrada

9
1 8 6 2 5 4 8 3 7

Salida

49

Ejemplo 2

Entrada

2
1 1

Salida

1

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