Candale Silviu (silviu) 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: Ai, Ai+1, …, Aj cu 1 ≤ i < j ≤ N. Prin lungimea secvenței înțelegem numărul de elemente care o compun.
Pentru orice secvenţă Ai, Ai+1, …, Aj, vom numi split-point un indice k, i ≤ k < j, care împarte secvența în două subsecvențe nevide: Ai, Ai+1, …, Ak, respectiv Ak+1, Ak+2, …, Aj.
Fie Dmax valoarea absolută maximă a diferenței sumelor elementelor celor două subsecvențe separate de un split-point, luând în considerare toate secvenţele Ai,Ai+1,…,Aj posibile şi fie Lmax lungimea maximă a unei secvenţe caracterizată de valoarea Dmax.
Cerinţă
Cunoscând N şi valorile elementelor şirului A, să se determine Dmax şi Lmax.
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 Dmax iar următoarea linie conţine numărul natural Lmax.
Restricții și precizări
2 ≤ N ≤ 100 000- elementele șirului
Asunt 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 Dmax este 6, adică: s1 = 2 + 3 = 5, s2 = -1, Dmax = |5 – (-1)|=6, Lmax = 3.
Se observă că există și secvența -1 5 pentru care : s1 = -1, s2 = 5, Dmax = |-1 – 5|=6 dar această secvență are lungimea 2.