1. Zlacnené disky

Matúš už vďaka vám našiel disk, ktorý má najlepší pomer ceny ku kapacite, ale stále nie je celkom spokojný. Momentálne je totiž spomenutý disk veľmi drahý. Po krátkej úvahe si Matúš uvedomil, že sa disky nevyrábajú v Európe, ale na Taiwane, a preto ich cena závisí od kurzu eura k taiwanskému doláru. Pohrabal sa v ekonomických zákutiach internetu a stiahol si vývoj kurzu na nasledujúcich \(n\) dní. Keďže potreboval disk ihneď, kúpil si ho na splátky priamo u taiwanskej spoločnosti.

Matúš každý deň spláca \(s\) eur, avšak ktorýkoľvek deň sa sa môže rozhodnúť doplatiť zvyšok sumy. Teraz už len potrebuje zistiť, ako dlho by mal platiť splátky a čakať so zaplatením zvyšku tak, aby dokopy zaplatil čo najmenej.

No a v súlade s jeho žgrlošským zmýšľaním prenechal Matúš túto úlohu lacnejšej pracovnej sile: vám!

Úloha

Na vstupe dostanete vývoj kurzu taiwanského doláru na najbližších \(n\) dní, cenu disku \(c\) v taiwanských dolároch a výšku splátky \(s\) v eurách. Matúš spláca každý deň \(s\) eur začínajúc prvým dňom, ktorý je na vstupe. Skutočnú sumu, ktorú dostane taiwanská spoločnosť vypočítame tak, že sumu, ktorú zaplatí Matúš v eurách vynásobíme kurzom na daný deň. Ak je kurz \(47\) a Matúš zaplatí \(2\) eurá, tak sa z celkovej sumy \(c\) odráta \(47\cdot 2=94\) taiwanských dolárov. Celková suma, ktorú dostane spoločnosť v taiwanských dolároch, môže byť aj vyššia, ako cena disku, keďže Matúš vie platiť iba celočíselné sumy.

Vašou úlohou je zistiť, v ktorý deň má Matúš zaplatiť zvyšok dlhu, aby dokopy zaplatil čo najmenej eur. Ak je takých dní viac, vypíšte ten najskorší, aby Matúš splácal čo najkratšie. V prípade, že sa mu oplatí čakať až do \(n\)-tého dňa, musí Matúš vyplatiť zvyšok sumy v tento deň. Matúš musí aj v posledný deň splácania zaplatiť aspoň \(s\) eur.

Formát vstupu

V prvom riadku vstupu sú tri kladné celé čísla \(n\), \(c\) a \(s\) (\(1 \leq n \leq 200\,000, 1 \leq c,s \leq 10^9\)) udávajúce počet dní pre ktoré poznáme kurz, cenu disku a výšku splátky. V nasledujúcom riadku je \(n\) celých čísel oddelených medzerou, kde číslo na pozícií \(i\) udáva kurz v \(i\)-tom dni.

Formát výstupu

Vypíšte jedno číslo – taký deň, v ktorom má Matúš doplatiť zvyšok sumy, aby dokopy zaplatil čo najmenej. Nezabudnite za ním vypísať koniec riadku.

Príklad

Input:

5 1000 2
3 47 190 50 30

Output:

3

V prvý deň zaplatí \(2\cdot 3=6\) dolárov, druhý deň \(2\cdot 47=94\) a tretí deň doplatí zvyšok \(5\cdot 190=950\).

Input:

4 200 10
3 2 10 20

Output:

3

V tretí deň zaplatí \(15\) eur, takže dokopy zaplatí 35 eur v hodnote \(10\cdot 3+10\cdot 2+15\cdot 10=200\) dolárov. Ak by čakal na najvyšší kurz vo štvrtý deň, zaplatil by dokopy \(40\) eur, pretože aj v posledný deň splácania musí Matúš zaplatiť aspoň \(10\) eur.

Input:

3 1000 1
100 10 1

Output:

1

Matúš sa môže rozhodnúť, že zaplatí celú sumu aj v prvý deň.