0x50 - Rectángulo de máxima área dentro de un histograma enorme

Este problema es idéntico al problema 0x4f - Rectángulo de máxima área en un histograma pequeño pero con una entrada mucho más grande.

En la avenida principal de Ciudad Codeo hay N edificios numerados de 0 a N-1 de izquierda a derecha.

Los edificios podrían tener diferentes alturas (aunque también es posible que haya edificios con exactamente la misma altura). Aquí hay un ejemplo con N = 8. Los números en el eje vertical a la izquierda muestran la altura de los edificios, y los números en la escala horizontal abajo muestran la numeración de los edificios:

Una empresa importante de Ciudad Codeo quiere poner una valla publicitaria en la fachada de los edificios. La valla debe ser un rectángulo con bordes completamente horizontales o verticales.

La valla puede ser tan ancha cómo sea necesario pero su altura no puede exceder la altura de ninguno de los edificios detrás de ella (porque se necesita una superficia sólida detrás para instalarla correctamente). Aquí hay un ejemplo de una valla de altura 2 puesta entre los edificios 1 y 5:

Todos los edificios miden una unidad de ancho. Esta valla mide entonces 2 unidades de alto y 5 unidades de ancho, y por lo tanto tiene un área total de 2 x 5 = 10 unidades.

Para que la campaña publicitaria sea lo más efectiva posible, queremos que la valla tenga la máxima área que pueda alcanzarse. En este caso, si ponemos una valla de 4 unidades de altura entre los edificios 2 a 4 su área sería de 12 unidades (que es la máxima posible en este ejemplo):

(Aclaración: esta no es la única manera de lograr una valla de 12 unidades de área. También podemos lograrlo con una valla de altura 3 entre los edificios 1 y 4.)

Escribe un programa que recibe la altura de todos los edificos y calcula la máxima área posible que puede tener la valla.

Entrada

La entrada contiene dos líneas:

• La primera línea contiene N, el número de edificios.
• La segunda línea contiene N enteros Ai para 0 ≤ i < N, la altura de todos los edificios de izquierda a derecha. Estos números están separados por espacios. Está garantizado que Ai satisface 1 ≤ Ai ≤ 109.

Salida

La salida debe tener exactamente una línea con un entero: la máxima área posible para la valla.

Entrada de ejemplo 1

8
1 3 6 5 4 2 1 2

Salida de ejemplo 1

12

Explicación del ejemplo 1

La entrada nos da los edificios de la imagen del ejemplo más arriba. La máxima área que podemos cubrir con la valla es 12 (y hay varias maneras de lograrlo, como ya se explicó).

Entrada de ejemplo 2

3
2 7 2

Salida de ejemplo 2

7

Explicación del ejemplo 2

Si un edificio es suficientemente alto, vale la pena poner una valla estrecha pero muy alta:

Entrada de ejemplo 3

3
2 3 2

Salida de ejemplo 3

6

Explicación del ejemplo 3

En este caso ya no vale la pena poner la valla en un sólo edificio y es mejor ponerla en varios edificios:

Entrada de ejemplo 4

3
2 2 2

Salida de ejemplo 4

6

Explicación del ejemplo 4

Si todos los edificios tienen la misma altura, la valla de mayor área cubre todos los edificios en su totalidad:

Restricciones

• Está garantizado que en todas las entradas N satisface 1 ≤ N ≤ 100,000.

Envía tu solución