Se da un sir de n numere naturale nenule a_1, a_2, ..., a_n si Q intrebari. Fiecare intrebare contine doua numere x si s. Raspunsul la intrebare este cel mai mare numar p (0 <= p <= n) cu proprietatea ca primele p elemente ale sirului sunt toate mai mici sau egale cu x, iar suma lor este mai mica sau egala cu s. Raspundeti la toate intrebarile.
- Date de intrare
- Pe prima linie se afla n. Pe a doua linie se afla cele n numere ale sirului. Pe a treia linie se afla Q, iar pe fiecare dintre urmatoarele Q linii cate doua numere x si s.
- Date de iesire
- Se afiseaza Q linii; linia k contine raspunsul la a k-a intrebare.
- Restrictii
- 1 <= n, Q <= 200 000 1 <= a_i <= 1 000 000 000 1 <= x <= 1 000 000 000 1 <= s <= 1 000 000 000 000 000
Exemple
Exemplul 1
Intrare
8 3 1 4 1 5 9 2 6 6 4 100 9 20 2 50 10 3 10 31 100 1000
Iesire
4 5 0 1 8 8
Exemplul 2
Intrare
4 5 5 5 5 3 5 15 4 100 5 20
Iesire
3 0 4