Egy körbefűzött nyakláncon N darab (N páros), különböző értékű gyöngy van. A nyakláncot az i-edik gyöngy után elvághatjuk. Az egyes gyöngyök értéke a vágás helyétől vett kisebb távolsággal megszorzódik (a két közvetlen szomszéd éréke egyszeres, az eggyel távolabbiak kétszeres, a még eggyel távolabbiak háromszoros értékűek lesznek, ... és így tovább). 

Írjunk programot, ami megadja, hogy hol vágjuk el a nyakláncot, hogy az összérték a lehető legnagyobb legyen!

A bemenet első sorában a gyöngyök száma (3 <= N <= 1000000) van. A következő N sor mindegyike egy egész számot tartalmaz, közülük az i-edik az i-edik gyöngy értékét (1 <= érték_i <= 100).

Egyetlen sorába annak a gyöngynek a sorszámát kell írni, amely után elvágva a nyakláncot, a gyöngyök összértéke a lehető legnagyobb lesz! Több megoldás esetén bármelyik megadható.

Bemenet	Kimenet
4 30 30 10 20	3

A feladat forrása: NTOITV 3. forduló, 11-13. évfolyam

Algoritmusok: 

megoldás