Rezolvare PBinfo #4433

Se dă un șir V ce conține N numere întregi numerotate începând de la 1: V[1], V[2], ..., V[N] și două numere naturale nenule K și L, cu proprietatea că: 1 ≤ K ≤ L ≤ 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], ..., V[poz+L-1], valoarea elementului de pe poziția a K-a în cadrul secvenței este V[poz+K-1].

Cerința

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 ≤ i ≤ Q.

Restricții și precizări

• 2 ≤ N ≤ 300.000 și 1 ≤ Q ≤ 300.000.
• −50 000 ≤ V[i] ≤ 50.000, pentru fiecare i: 1 ≤ i ≤ N.
• 1 ≤ poz ≤ 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ă.
• Datorită dimensiunilor, nu toate testele au putut fi adăugate.

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.