Rezolvare PBinfo #3709

Se citește un număr n și apoi n numere naturale. Numim secvență un grup de elemente aflate pe poziții consecutive în șirul citit. Numim tri-secvență o secvență care începe cu un element impar, se termină cu un element impar și care mai conține în interior exact un element impar. Astfel, fiecare tri-secvență include două secvențe maximale formate doar din elemente pare (eventual, fiecare dintre cele două poate fi vidă). Dezechilibrul unei tri-secvențe se calculează astfel: determinăm suma elementelor din secvența din stânga formată doar din elemente pare, suma elementelor din secvența din dreapta formată doar din elemente pare și apoi diferența în modul a celor două valori (adică scădem din cea mare pe cea mică). Dacă vreuna dintre cele două secvențe de elemente pare este vidă, aceasta se consideră de sumă 0. Această diferență reprezintă dezechilibrul tri-secvenței.

Cerința

Să se determine o tri-secvența de dezechilibru minim. Dacă sunt mai multe astfel de tri-secvențe, să se determine cea care începe la o poziție cât mai mare.

Date de intrare

Fișierul de intrare tri.in conține pe prima linie un număr natural n ce reprezintă numărul de elemente ale șirului dat. Pe a doua linie sunt n numere naturale reprezentând elementele șirului, în ordinea crescătoare a pozițiilor, numerotate începând cu 1. În testele de intrare se dă n pe un rând iar elementele șirului pe rândul
următor separate prin câte un spațiu.

Date de ieșire

Fișierul de ieșire tri.out va conține pe prima linie două numere naturale cuprinse între 1 și n (inclusiv), separate printr-un spațiu, reprezentând poziția de început, respectiv cea de final a tri-secvenței determinate.

Restricții și precizări

• 3 ≤ n ≤ 100.000
• 0 ≤ valoarea unui element ≤ 1.000.000.000
• Șirul conține cel puțin 3 elemente impare

Exemplu:

tri.in

16
2 3 8 7 4 2 5 10 7 9 8 11 8 2 13 6

tri.out

10 15

Explicație

Avem 5 tri-secvențe: 3 8 7 4 2 5, cu dezechilibrul 2; 7 4 2 5 10 7, cu dezechilibrul 4; 5 10 7 9, cu
dezechilibrul 10; 7 9 8 11, cu dezechilibrul 8; 9 8 11 8 2 13, cu dezechilibrul 2.