Fie un şir  a₁, a₂, ..., a_N  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 a_x, a_x+1, ..., a_y. 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 a_x, a_x+1, ..., a_y 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 a₁, a₂, ..., a_N.

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 a_x, a_x+1, ..., a_y.

Restricţii

• 2<= N <= 100 000
• -1000 <= a_i <= 1000 pentru orice i=1..N
• Secvenţa a_x, a_x+1, ..., a_y 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.

prof. Dan Pracsiu

Liceul "Stefan Procopiu" Vaslui

dpracsiu@yahoo.com

prof. Adrian Panaete

Colegiul National "A.T.Laurian" Botosani

acpanaete@yahoo.com