La marginea unei păduri sunt N stupi aşezaţi în linie. Ei au asociate numere de ordine de la 1 la N, în ordinea în care apar. Fiind sezonul florii de salcâm, albinele colectează foarte repede mierea. La finalul fiecărei zile, din satul aflat în apropiere vine un apicultor la volanul unui camion pentru a o recolta. Capacităţile camioanelor pot fi diferite. Procesul de strângere a mierii decurge astfel: camionul pleacă din dreptul stupului 1 şi încarcă întreaga cantitate de miere din acesta, apoi trece la stupul 2 şi procedează la fel şi aşa mai departe. Dacă odată ajuns la un stup camionul nu poate colecta întreaga cantitate de miere din acel stup, acesta întrerupe acţiunea de colectare şi se întoarce în sat. În ziua următoare, albinele din stupii de unde s-a recoltat refac cantitatea de miere din ziua anterioara. În plus, în fiecare stup cantitatea de miere creşte cu un kilogram faţă de ziua anterioară.

Cerința

Dându-se N, numărul de stupi, cantitatea de miere existentă în fiecare la finalul primei zile, numărul M de zile în care se face colectarea mierii şi capacitatea camionului care trece în fiecare zi, se cere numărul de stupi din care se recoltează miere în fiecare dintre cele M zile.

Date de intrare

Fişierul miere.in are următoarea structură:

• pe prima linie N, numărul de stupi;
• pe linia a 2-a, N numere naturale, separate prin câte un spaţiu. Numerele reprezintă cantitatea de miere din cei N stupi la finalul primei zile, în ordinea de la 1 la N;
• pe linia a 3-a M, numărul de camioane;
• pe linia a 4-a, M numere naturale separate prin câte un spaţiu. Numerele reprezintă capacităţile camioanelor, în ordinea în care sosesc.

Date de ieșire

Fişierul miere.out conţine M numere naturale, fiecare pe câte o linie. Pe linia i se află numărul de stupi din care colectează miere camionul i.

Restricții și precizări

• cantităţile de miere produse de fiecare stup şi capacităţile camioanelor sunt precizate în kilograme.
• 1 <= N, M <=50000
• e posibil ca un camion sa nu poată colecta miere din niciun stup sau sa poată colecta mierea din toţi stupii
• suma cantităţilor de miere din toţi stupii din fiecare moment şi capacităţile camioanelor sunt numere naturale strict pozitive şi mai mici decât 263.

Exemplu

miere.in

4
2 3 1 7
2
5 6

miere.out

2
1

Explicație

În prima zi camionul colectează în întregime cantitatea de miere din primii 2 stupi. La finalul celei de-a doua zile, cantităţile de miere din fiecare stup sunt: 3 4 2 8. Camionul, care vine în a doua zi are capacitatea 6, deci el colectează mierea din primul stup dar nu mai poate colecta în întregime din al doilea, aşa că se întoarce şi pleacă.

#include <bits/stdc++.h>


using namespace std;

ifstream cin("miere.in");
ofstream cout("miere.out");

long long s[50002] , x;
int n , m;

int cauta_bin(long long s[] , int n , long long x , int z)
{
    int st = 1 , dr = n;
    while(st <= dr)
    {
        int mij = (st + dr) / 2;
        if(s[mij] + 1ll * mij * (z - 1) > x) dr = mij - 1;
        else st = mij + 1;
    }
    return dr;
}

int main()
{
    cin >> n;
    for(int i = 1 ; i <= n ; i++)
    {
        cin >> s[i];
        s[i] += s[i - 1];
    }
    cin >> m;
    for(int i = 1 ; i <= m ; i++)
    {
        cin >> x;
        cout << cauta_bin(s , n , x , i) << '\n';
    }
}