ksplit

Se consideră un șir $A$ cu $N$ elemente întregi nenule. Numim secvență a șirului $A$ orice succesiune de elemente aflate pe poziții consecutive în șir: $A_i, A_{i+1}, \dots, A_j$ cu $1 \leq i < j \leq N$.

Prin lungimea secvenței înțelegem numărul de elemente care o compun. Pentru orice secvenţă $A_i, A_{i+1}, \dots, A_j$, vom numi split-point un indice $k$, $i \leq k < j$, care împarte secvența în două subsecvențe nevide: $A_i, A_{i+1}, \dots, A_k$, respectiv $A_{k+1}, A_{k+2}, \dots, A_j$.

Fie $D_{max}$ valoarea absolută maximă a diferenței sumelor elementelor celor două subsecvențe separate de un split-point, luând în considerare toate secvenţele $A_i, A_{i+1}, \dots, A_j$ posibile şi fie $L_{max}$ lungimea maximă a unei secvenţe caracterizată de valoarea Dmax.

Cerinţă

Cunoscând $N$ şi valorile elementelor şirului $A$, să se determine $D_{max}$ şi $L_{max}$.

Date de intrare

Fişierul de intrare ksplit.in conţine pe prima linie un număr natural $N$ ce reprezintă numărul de elemente al șirului $A$, iar pe cea de-a doua linie $N$ numere întregi nenule despărțite prin câte un spațiu.

Date de ieșire

Fişierul de ieşire ksplit.out va avea două linii. Prima linie conține numărul natural $D_{max}$ iar următoarea linie conţine numărul natural Lmax.

Restricții și precizări

• $2 \leq N \leq 100 \ 000$
• elementele șirului $A$ sunt numere întregi nenule din intervalul $[-1 \ 000 \ 000, 1 \ 000 \ 000]$

Exemplu

ksplit.in

4
2 3 -1 5

ksplit.out

6
3

Explicație

Dintre toate secvențele ce se pot forma, se alege secvența $2 \ 3 \ -1$, care este formată din primele $3$ elemente ale șirului.
Valoarea $D_{max}$ este $6$, adică: $s_1 = 2 + 3 = 5$, $s_2 = -1$, $D_{max} = |5 - (-1)| = 6$, $L_{max} = 3$.
Se observă că există și secvența $-1 \ 5$ pentru care: $s_1 = -1$, $s_2 = 5$, $D_{max} = |-1 - 5| = 6$ dar această secvență are lungimea $2$