Exista n statii de benzina asezate in cerc, numerotate de la 1 la n. Statia i ofera gas[i] combustibil, iar deplasarea de la statia i la statia urmatoare (i+1, sau de la n la 1) consuma cost[i] combustibil. Determinati, folosind metoda Greedy, indicele statiei de pornire din care, avand rezervorul initial gol, se poate parcurge tot circuitul o singura data in sensul dat, fara a ramane fara combustibil. Se garanteaza ca, daca exista, aceasta statie este unica.
- Date de intrare
- Pe prima linie se citeste n. Pe a doua linie se citesc cele n valori gas[i]. Pe a treia linie se citesc cele n valori cost[i].
- Date de iesire
- Se afiseaza indicele (numerotat de la 1) statiei de pornire, sau -1 daca nu exista o astfel de statie.
- Restrictii
- 1 <= n <= 100000, 0 <= gas[i], cost[i] <= 10^9
Exemple
Exemplul 1
Intrare
5 1 2 3 4 5 3 4 5 1 2
Iesire
4
Exemplul 2
Intrare
3 2 3 4 3 4 3
Iesire
-1