Se da un sir de n numere naturale nenule a_1, a_2, ..., a_n. Sirul trebuie taiat in trei secvente consecutive si nevide, alegand doi indici i < j: prima secventa este a_1, ..., a_i, a doua este a_{i+1}, ..., a_j, iar a treia este a_{j+1}, ..., a_n.
Pentru o taiere, notam cu D diferenta dintre cea mai mare si cea mai mica dintre cele trei sume ale secventelor. Determinati taierea pentru care D este minim. Daca exista mai multe astfel de taieri, se alege cea cu i minim, iar dintre acestea cea cu j minim.
- Date de intrare
- Pe prima linie se afla n, iar pe a doua linie cele n numere ale sirului.
- Date de iesire
- Se afiseaza cei doi indici i si j, separati printr-un spatiu.
- Restrictii
- 3 <= n <= 200 000 1 <= a_k <= 10 000
Exemple
Exemplul 1
Intrare
8 2 4 1 3 6 2 2 5
Iesire
3 5
Exemplul 2
Intrare
5 1 1 1 1 1
Iesire
1 3