kth

Se dă un șir $V$ ce conține $N$ numere întregi numerotate începând de la $1$: $V_1, V_2, \ldots, V_N$ și două numere naturale nenule $K$ și $L$, cu proprietatea că: $1 \leq K \leq L \leq N$. Mihai studiază doar secvențele de lungime $L$, adică secvențele formate din exact $L$ elemente situate pe poziții alăturate în acest șir $V$.

El își poate pune următoarea întrebare: „Dacă aș rearanja, în ordine crescătoare, elementele secvenței de lungime $L$ care începe la poziția $poz$ în șirul $V$, ce valoare s-ar afla pe poziția a $K$-a în cadrul secvenței rezultate?”.
Pentru secvența din șir care începe la poziția $poz$ și are $L$ elemente, adică $V_{poz}, V_{poz+1}, \ldots, V_{poz+L-1}$, valoarea elementului de pe poziția a $K$-a în cadrul secvenței este $V_{poz+K-1}$.

Cerință

Ajutați-l pe Mihai să afle care este răspunsul corect pentru $Q$ întrebări de tipul descris mai sus!

Date de intrare

Pe prima linie a fișierului de intrare kth.in se află trei numere naturale nenule $N$, $K$ și $L$, separate între ele prin câte un spațiu, cu semnificațiile de mai sus. Pe următoarea linie se află, separate între ele prin câte un spațiu, $N$ numere întregi, reprezentând, în ordine, elementele șirului $V$. Pe următoarea linie se află numărul natural nenul $Q$, reprezentând numărul de întrebări formulate de către Mihai. Pe fiecare dintre următoarele $Q$ linii se află câte un număr natural nenul $poz$, reprezentând poziția de început a secvenței de $L$ elemente pentru care se pune întrebarea respectivă.

Date de ieșire

Fișierul de ieșire kth.out va conține $Q$ linii. Pe linia $i$ se va afla un număr întreg ce reprezintă răspunsul la întrebarea $i$, în ordinea dată în fișierul de intrare, pentru fiecare $i$: $1 \leq i \leq Q$.

Restricții și precizări

• $2 \leq N \leq 300 \ 000$ și $1 \leq Q \leq 300 \ 000$;
• $-50 \ 000 \leq V_i \leq 50 \ 000$, pentru fiecare $i$: $1 \leq i \leq N$;
• $1 \leq poz \leq N - L + 1$, pentru fiecare dintre cele $Q$ întrebări;
• Valorile $poz$ din cadrul celor $Q$ întrebări nu sunt neapărat distincte între ele oricare două.

Exemplul 1

kth.in

5 2 3
4 -5 2 1 4
2
2
1

kth.out

1
2

Explicație

Sunt $N = 5$ elemente în șirul $V = (4, -5, 2, 1, 4)$. Pentru prima întrebare (pentru care $poz = 2$), dacă secvența formată din $L=3$ elemente: $(V_2, V_3, V_4)$ ar fi ordonată crescător, aceasta ar deveni: $(-5, 1, 2)$, ceea ce înseamnă că pe cea de a doua ($K=2$) poziție în cadrul ei s-ar afla valoarea $1$.

Exemplul 2

kth.in

5 2 3
1 5 2 4 3
2
2
1

kth.out

4
2

Explicație

Sunt $N = 5$ elemente în șirul $V = (1, 5, 2, 4, 3)$, $K=2$ și $L=3$.
$Q=2$ întrebări formulate.