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, S1 sendo os checkpoints antes de seu descanso (incluindo o que você irá parar) e S2 sendo os checkpoints depois de seu descanso, tal que tamanho(S1)+tamanho(S2)=N (i.e. todo checkpoint pertence a um exato sub-array).
A beleza total da jornada é definida por soma(S1)∗soma(S2) onde soma(S) é a soma total do valor de beleza no sub-array S. Você quer maximizar o valor de soma(S1)∗soma(S2).
Entrada
A primeira linha de entrada contém um inteiro N(2≤N≤105), denotando o número de checkpoints. A segunda linha contém N inteiros separados, denotando o valor de beleza dos checkpoints (1≤Ai≤104).
Saída
Você tem que apresentar o valor maximo de soma(S1)∗soma(S2).
soma(s1)∗soma(s2) irá ser o máximo quando s1=[1,2,3] e s2=[4,5]. soma(s1)=6 e soma(s2)=9, então soma(s1)∗soma(s2)=54.
