Koliko ih je do x
Zadana je lista od N brojeva i Q pitanja. Za svako pitanje x ispiši koliko je brojeva u listi manje ili jednako x.
- Ulaz
U prvom retku N, u drugom N brojeva. U trećem retku Q, u četvrtom Q brojeva x.
- Izlaz
Q redaka s odgovorima.
- Ograničenja
1 ≤ N, Q ≤ 100 000, brojevi su od 1 do 1 000 000 000
Primjer 1
Ulaz
5 7 2 9 2 5 4 2 6 1 9
Izlaz
2 3 0 5
Zapeo si?
Prvo pokušaj sam. Savjeti se otvaraju jedan po jedan, svaki otkriva malo više.
Sortiraj jednom, pa za svako pitanje binarno traži.
Koliko je elemenata ≤ x? Razmisli gdje u sortiranoj listi završavaju brojevi ≤ x.