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ă.