Точка на рамнотежа
Мечето Мендо на лист хартија има запишано низа од N природни броеви, и сака да дознае дали таа низа има елемент кој претставува точка на рамнотежа. Точка на рамнотежа на дадена низа е елемент од таа низа за кој што важи својството дека збирот на сите елементи лево од тој елемент е еднаков на збирот на сите елементи десно од тој елемент. Да забележиме дека не е дозволена промена на позициите на елементите.
Формално, точка на рамнотежа на низа A е елемент Ai од низата таков што A1 + A2 + … + Ai-1 = Ai+1 + Ai+2 + … + AN. Доколку не постојат елементи лево или десно од некој елемент, се смета дека соодветниот збир е еднаков на 0.
Влез
Во првиот ред се наоѓа еден број N (1 ≤ N ≤ 100 000), кој го претставува бројот на елементи во низата. Во вториот ред се дадени N броеви Ai (1 ≤ Ai ≤ 10 000), разделени со по едно празно место, кои ја сочинуваат низата.
Забелешка:
За 5% од поените ќе важи N=3.
За дополнителни 35% од поените ќе важи N≤10 000.
Излез
Единствената линија од излезот треба да го даде редниот број i на елементот Аi кој е точката на рамнотежа на низата на Мендо (низата е индексирана со броеви од 1 до N, вклучително). Доколку низата не содржи елемент кој е точка на рамнотежа, треба да се испечати -1.
Ограничувања
Временско ограничување: 1 second
Мемориско ограничување: 64 megabytes
Примери
влез 4 1 2 3 3 | излез 3 |
влез 1 5 | излез 1 |
влез 5 4 5 1 3 2 | излез -1 |
Објаснување за првиот тест пример: Третиот елемент Аi=3 е точка на рамнотежа затоа што сумата на елементи лево и десно од тој елемент е иста т.е. 1+2=3.
Објаснување за вториот тест пример: Сумата лево и десно од првиот елемент на низата Аi=5 е 0.