Rezolvare PBinfo #2273

Se consideră un șir a[1], a[2], …, a[n] de numere naturale nenule. Pentru doi indici 1 ≤ i < j < n, notăm cu X = a[1] + a[2] + ... + a[i], Y = a[i+1] + a[i+2] + ... + a[j] și Z = a[j+1] + a[j+2] + ... + a[n].

Cerința

Să se determine doi indici i și j astfel încât diferența max(X, Y, Z) - min(X, Y, Z) să fie minimă.

Date de intrare

Programul citește de la tastatură numărul n, iar apoi șirul de n numere naturale, separate prin spații.

Date de ieșire

Programul va afișa pe ecran valorile indicilor i și j. Dacă sunt mai multe soluții, se va afișa aceea pentru care i este minim, iar dacă sunt mai multe soluții cu același i minim, se va afișa aceea cu indicele j minim.

Restricții și precizări

• 1 ≤ n ≤ 200 000
• 1 ≤ a[i] ≤ 10 000

Exemplu:

Intrare

10
1 3 4 2 1 2 10 5 8 6

Ieșire

6 8

Explicație

i = 6 și j = 8. În acest caz X = 13, Y = 15, Z = 14. Diferența este max(X, Y, Z) - min(X, Y, Z) = 15-13 = 2. Nu există o împărțire pentru care diferența să fie mai mică.