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.

enter image description here

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)\).