La proba de sărituri cu schiurile din cadrul jocurilor olimpice de iarnă participă N concurenţi, numerotaţi cu numere de la 1 la N.
Regulile de desfăşurare a probei sunt următoarele:
- concurenţii evoluează pe rând, în ordine de la 1 la N;
- fiecare concurent va efectua o singură săritură;
- după efectuarea săriturii fiecare concurent primeşte un anumit punctaj;
- pe tot parcursul concursului, comisia de arbitri are obligaţia să alcătuiască o listă cu punctajele obţinute de concurenţi, în ordinea evoluţiei lor;
- evoluţia unui concurent durează exact un minut;
- nu se face pauză între evoluţiile a doi concurenţi care au numere de ordine consecutive;
- afişarea punctajului nu necesită timp suplimentar după efectuarea săriturii;
- proba se încheie la un minut după evoluţia ultimului concurent.
Pe tot parcursul concursului se ţine în mod neoficial şi un clasament parţial, pe baza rezultatelor obţinute de concurenţii care au evoluat până în acel moment. Asta pentru că şeful comisiei de arbitri are o curiozitate aparte şi pune K întrebări sub forma următoare: „Câte minute s-a ocupat primul loc din clasament cu un punctaj egal cu X puncte”? Dacă nici un concurent nu s-a clasat pe primul loc cu X puncte atunci primeşte ca răspuns valoarea 0.
Cerinţă
Scrieţi un program care determină răspunsul pentru fiecare dintre cele K întrebări puse de şeful comisiei de arbitri.
Date de intrare
În fişierul schi1.in, pe prima linie este scris un număr natural, N reprezentând numărul de concurenţi. Pe a doua linie a fişierului sunt scrise cele N numere naturale separate prin câte un spaţiu, reprezentând punctajele obţinute de fiecare dintre cei N concurenţi, în ordinea în care aceştia au evoluat. Pe a treia linie a fişierului este scris numărul natural K ce reprezintă numărul de întrebări puse de şef. Pe a patra linie a fişierului sunt scrise K numere naturale separate prin câte un spaţiu, reprezentând valorile X ale punctajelor alese de şeful comisiei de arbitri.
Date de ieşire
În fişierul schi1.out se vor scrie K numere, separate prin câte un spaţiu, reprezentând, în ordine, răspunsurile la cele K întrebări.
Restricţii
• 1 ≤ N ≤ 100 000
• 1 ≤ K ≤ 100 000
• 0 ≤ punctajele obţinute de concurenţi ≤ 1 000 000 000
• 0 ≤ valorile X alese de şeful arbitrilor ≤ 1 000 000 000
Exemple
schi1.in
schi1.out
Explicaţii
10
1 6 5 3 6 8 8 6 1 9
6
5 1 6 8 2 9
0 1 4 4 0 1
Cu punctajul 5 nu s-a ocupat niciodată locul 1, cu punctajul 1 s-a ocupat primul loc un singur minut, cu punctajele 6 şi 8 s-a ocupat locul 1 câte 4 minute. Cu punctajul 2 nu s-a ocupat locul 1. El nici nu a fost obţinut de vreun concurent. Cu punctajul 9 s-a ocupat locul 1 un minut.