A BR-101 (Também chamada de Translitorânea, oficialmente nomeada Rodovia Governador Mário Covas) é uma estrada longitudinal do Brasil. É a mais longa do país.

A estrada tem N checkpoints. Cada checkpoint tem um valor de beleza denotado como um array A em ordem do ínício da estrada até o final da mesma. O valor de beleza de um checkpoint consiste na beleza dos lugares próximos ao checkpoint. Você está planejando viajar pela estrada. Como é uma longa estrada, você irá parar em um dos checkpoints para um pouco de descanso e após este descanso, contiuar sua jornada.

Então, sua jornada em dois sub-arrays próximos, $S_1$ sendo os checkpoints antes de seu descanso (incluindo o que você irá parar) e $S_2$ sendo os checkpoints depois de seu descanso, tal que $tamanho(S_1) + tamanho(S_2) = N$ (i.e. todo checkpoint pertence a um exato sub-array).

A beleza total da jornada é definida por $soma(S_1) * soma(S_2)$ onde $soma(S)$ é a soma total do valor de beleza no sub-array S. Você quer maximizar o valor de $soma(S_1) * soma(S_2)$.

Entrada

A primeira linha de entrada contém um inteiro $N (2 \le N \le 10^5)$, denotando o número de checkpoints. A segunda linha contém N inteiros separados, denotando o valor de beleza dos checkpoints $(1 \le A_i \le 10^4 )$.

Saída

Você tem que apresentar o valor maximo de $soma(S_1) * soma(S_2)$.