Fie un şir a1, a2, ..., aN de numere întregi. În acest şir se alege o pereche de indici (x, y) cu 1 <= x <= y <= N şi se inversează semnul tuturor componentelor secvenţei ax, ax+1, ..., ay. De exemplu, pentru şirul 3, -5, 4, -1, 6, -8, -5, dacă se alege perechea (3, 5), atunci şirul va deveni 3, -5, -4, 1, -6, -8, -5.
Cerinţă
Să se determine o pereche de indici x, y astfel încât după inversarea semnului componentelor secvenţei ax, ax+1, ..., ay suma elementelor din vector să fie minimă.
Date de intrare
Fişierul de intrare sminus.in conţine pe prima linie valoarea N. Pe a doua linie, separate prin câte un spaţiu, se găsesc numerele întregi a1, a2, ..., aN.
Date de ieşire
Fişierul de ieşire sminus.out conţine două linii. Pe prima linie se vor găsi două numere naturale x şi y separate printr-un spaţiu reprezentând perechea de indici. Pe linia a doua se va găsi un singur număr natural reprezentând suma minimă obţinută prin inversarea semnului componentelor din secvenţa ax, ax+1, ..., ay.
Restricţii
2<= N <= 100 000
-1000 <= ai <= 1000 pentru orice i=1..N
Secvenţa ax, ax+1, ..., ay trebuie să conţină cel puţin un element.
Dacă există mai multe soluţii pentru perechea (x, y), atunci se va alege aceea care are indicele x minim, iar dacă sunt mai multe secvenţe posibile care încep la poziţia x, se va alege aceea care are valoarea y maximă.
Pentru teste valorând 50 de puncte, N <= 2000.
Exemplu
sminus.in
sminus.out
Explicaţii
7
3 -5 4 -1 6 -8 -5
3 5
-24
Inversând semnul elementelor din secvenţa care începe la poziţia 3 şi se termină la poziţia 5 se obţine secvenţa 3, -5, -4, 1, -6, -8, -5 care are suma elementelor egală cu -24.