Longest walk

Cerință

Într-un tărâm îndepărtat, trăiau doi prieteni, Ana și Bogdan. În lipsă de activități, cei doi organizează în fiecare zi câte o plimbare. Tărâmul poate fi văzut ca o înșiruire $N$ de dealuri, de diverse înălțimi. De-a lungul unei zile, fiecare dintre cei doi prieteni pleacă de pe un deal la alegere (pot alege același deal), și se depleaseaza către dreapta, de pe un deal având voie să meargă doar următorul deal a cărei înălțime este mai mare sau egală cu cea a dealului curent. Aceștia se opresc când ajung în primul deal in care pot ajunge amandoi (acesta poate fi cel din care au pornit), iar distanța parcursă este dată de numărul total de dealuri prin care aceștia au trecut.
Există $Q$ zile în calendar, iar în fiecare zi, cei doi prieteni își propun sa meargă o distanța de exact $q_i$ unități. Ana și Bogdan vă cer ajutorul, și vor sa le spuneți pentru fiecare zi dacă există cel puțin o posibilitate de unde aceștia pot începe, astfel încât, respectând regulile prezentate, aceștia să parcurgă distanța totală dorită.

Date de intrare

Pe prima linie a fișierului de intrare longest-walk.in se găsește un număr natural $N$.
A doua linie va conține $N$ numere, reprezentând înalțimile dealurilor, $H_i$, în ordinea in care sunt poziționate.
A treia linie va conține numărul de zile $Q$.
A patra linie va conține $Q$ numere, reprezentând distanțele dorite pentru fiecare zi in parte.

Date de ieșire

Fișierului de ieșire longest-walk.out va conține $Q$ linii, cu o valoare pe fiecare line, $0$ sau $1$, reprezentând răspunsurile celor $Q$ zile, în ordinea în care acestea au fost date.

Restricții și precizări

• Pentru teste în valoare de 30 de puncte, $1 \leq N, Q \leq 200$;
• Pentru teste în valoare de 30 de puncte, $1 \leq N, Q \leq 2 \ 000$;
• $1 \leq N, Q \leq 100 \ 000$;
• $1 \leq H_i \leq 1\ 000 \ 000 \ 000$;
• $1 \leq q_i \leq 1 \ 000 \ 000$;

Exemplul 1

longest-walk.in

10
6 7 3 2 1 4 5 8 9 10
3
4 8 6

longest-walk.out

1
0
1