Un histograma tiene \(n\) barras de ancho \(1\), una al lado de la otra, con alturas \(h_0, \dots, h_{n-1}\). Encuentra el área del rectángulo más grande que cabe completamente dentro del histograma (sus lados son paralelos a los ejes).

Entrada

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

Salida

El área máxima. (Puede no caber en 32 bits.)

Ejemplo 1

Entrada

6
2 1 5 6 2 3

Salida

10

Ejemplo 2

Entrada

2
2 4

Salida

4

Basado en el problema 84 de LeetCode, Largest Rectangle in Histogram, adaptado a entrada y salida estándar; enunciado redactado para este juez. Es parte de la lista Grind 75 de Yangshun Tay.