Maxsecvk

Cerință

Avem: $n$, $k$ și un șir de $n$ numere naturale. Este o problemă la care trebuie să răspundem la un anumit tip de interogări. Descriem mai departe semnificația uneia: se dă o poziție $p$ din șir ($p \geq k$). Ne imaginăm că sunt ascunse elementele de pe poziții de la $p+1$ la $n$ (nu le cunoaștem valoarea), dar vedem elementele de pe poziții de la $1$ la $p$.

Știm că vom dori să aflăm maximul din fiecare secvență de lungime $k$ care se termină la poziții mai mari sau egale cu $p$. Dintre elementele pe care le vedem dorim să identificăm un număr minim (cât mai puține) astfel încât să fim siguri că putem afla maximele din secvențele indicate anterior indiferent ce valori ar avea elementele de pe poziții de la $p+1$ la $n$.

Date de intrare

Fișierul maxsecvk.in conține pe prima linie numerele $n$ și $k$ separate prin spațiu.
Pe linia a doua sunt $n$ numere naturale, separate prin spații, reprezentând elementele șirului dat.
Pe linia a treia este un număr $t$.
Pe linia a patra sunt $t$ numere naturale, separate prin spații, reprezentând pozițiile $p$ pentru fiecare interogare.

Date de ieșire

Fișierul maxsecvk.out va conține $t$ numere naturale reprezentând răspunsul pentru fiecare interogare, în ordinea în care acestea au apărut în fișierul de intrare.

Restricții și precizări

• $1 \leq n \leq 100 \ 000$;
• Elementele șirului dat sunt cuprinse între $0$ și $1 \ 000 \ 000 \ 000$ (inclusiv capetele).
• Elementele ascunse ar putea avea orice valoare, dar tot din intervalul $0$, $1 \ 000 \ 000 \ 000$ (inclusiv capetele).
• $1 \leq t \leq n$;
• Valorile de la interogări pot fi orice poziție din șir mai mare sau egală decât $k$.
• Valorile $p$ se pot repeta în fișierul de intrare.

Exemplu

maxsecvk.in

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

maxsecvk.out

1 2 2

Explicație

La interogarea cu $p = 5$ considerăm că șirul este 0 4 2 3 8 x x x x
Doar elementul cu valoarea $8$ (cel de pe poziția $5$) poate conta.

La interogarea cu $p = 4$ considerăm că șirul este 0 4 2 3 x x x x x
La secvența terminată la poziția $5$ ar putea fi maxim elementul cu valoatea $4$. La secvențele terminate la poziția $6$ și la poziții mai mari, ar putea fi maximul elementul cu valoarea $3$.