iarmaroc

În fiecare toamnă, într-un sat din inima Ardealului, se organizează iarmarocul tradițional. De-a lungul uliței principale, $N$ negustori își așază tarabele, care sunt numerotate de la stânga la dreapta de la $1$ la $N$. Pe fiecare tarabă $i$ $(1 \leq i \leq N)$ este expus un singur produs tradițional - de la covoare țesute manual, până la dulcețuri de casă. În funcție de calitate, fiecare produs $i$ $(1 \leq i \leq N)$ are o atractivitate pentru vizitatori, notată $a_i$.

Toți cei $Q$ vizitatori ai iarmarocului respectă o tradiție veche, moștenită din generație în generație, când cumpără produse. Tradiția cere ca fiecare vizitator $j$ $(1 \leq j \leq Q)$ să parcurgă un interval de tarabe consecutive $[l_j, r_j]$ $(1 \leq l_j \leq r_j \leq N)$, mergând de la stânga la dreapta. Cumpărarea produselor se realizează respectând un anumit ritual, realizat astfel:

• Când vizitatorul începe un ritual, produsul de la prima tarabă vizitată este întotdeauna interesant și va fi cumpărat.
• În continuare, un produs este cumpărat dacă atractivitatea lui este strict mai mare decât atractivitatea ultimului produs cumpărat.
• Ritualul este complet finalizat atunci când este cumpărat al $K$-lea produs, iar de la taraba imediat următoare va începe un nou ritual.

La sfârșitul vizitei în iarmaroc, satisfacția unui vizitator este egală cu numărul total de ritualuri de cumpărare complet finalizate.

Cerința

Cunoscând $N$ - numărul de tarabe, $K$ - numărul de produse care trebuie să fie cumpărate într-un ritual complet, $Q$ - numărul de vizitatori, $a_1, a_2, \ldots, a_N$ - atractivitatea celor $N$ produse expuse la tarabe, precum și $Q$ intervale $[l_j, r_j]$ $(1 \leq j \leq Q)$ - tarabele vizitate de fiecare dintre cei $Q$ vizitatori, scrieți un program care să determine satisfacția fiecărui vizitator, la finalul vizitei din iarmaroc.

Date de intrare

Fișierul de intrare iarmaroc.in conține pe prima linie trei numere naturale $N$, $K$ și $Q$, cu semnificația din enunț. Pe a doua linie se află numerele naturale $a_1, a_2, \ldots, a_N$, reprezentând, în ordine, atractivitatea produselor expuse la tarabe. Pe fiecare dintre următoarele $Q$ linii se află câte două numere naturale $l_j$ și $r_j$ reprezentând intervalul de tarabe parcurs de vizitatorul $j$ $(1 \leq j \leq Q)$. Valorile scrise pe aceeași linie sunt separate prin câte un spațiu.

Date de ieșire

Fișierul de ieșire iarmaroc.out va conține $Q$ linii. Pe a $j$-a linie se va afișa un singur număr natural, reprezentând satisfacția celui de-al $j$-lea vizitator $(1 \leq j \leq Q)$.

Restricții și precizări

• $1 \leq N, Q \leq 200 \ 000$
• $1 \leq K \leq N$
• $1 \leq a_i \leq 10^9$ pentru orice $1 \leq i \leq N$
• $1 \leq l_j \leq r_j \leq N$ pentru $1 \leq j \leq Q$

Exemplu

iarmaroc.in

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

iarmaroc.out

2
1
2
0

Explicație

Primul vizitator parcurge tarabele cu produsele având atractivitatea $[3, 1, 4, 1, 5, 9, 2, 6]$. Pentru a finaliza un ritual el trebuie să cumpere $K = 2$ produse.

Primul ritual:

• cumpără primul produs, cu atractivitatea $3$;
• trece peste produsul cu atractivitatea $1$ $(1 \leq 3)$;
• cumpără produsul cu atractivitatea $4$ $(4 > 3)$.

Deoarece a cumpărat $2$ produse, primul ritual este complet.

Al doilea ritual:

• cumpără produsul de la prima tarabă vizitată în continuare (cel cu atractivitatea $1$);
• produsul cu atractivitatea $5$ $(5 > 1)$.

Al doilea ritual este complet.

Începe al treilea ritual, și cumpără primul produs, având atractivitatea $9$, dar $2$ și $6$ nu depășesc $9$, deci al treilea ritual rămâne nefinalizat. Așadar, satisfacția primului vizitator este $2$.

Al doilea vizitator parcurge tarabele având produse cu atractivitatea $[4, 1, 5, 9, 2]$.

Primul ritual:

• cumpără produsul de la prima tarabă vizitată, cu atractivitatea $4$;
• trece peste produsul cu atractivitatea $1$ $(1 \leq 4)$;
• cumpără produsul cu atractivitatea $5$ $(5 > 4)$.

Primul ritual este complet.

Începe al doilea ritual, cumpără produsul cu atractivitatea $9$, apoi nu mai poate cumpăra niciun produs, deci acest ritual rămâne incomplet. La final, satisfacția sa este $1$.

Al treilea vizitator parcurge tarabele cu produsele având atractivitatea $[1, 4, 1, 5]$.

Primul ritual:

• cumpără produsul de la prima tarabă vizitată, cu atractivitatea $1$;
• cumpără produsul cu atractivitatea $4$ $(4 > 1)$.

Primul ritual este complet.

Al doilea ritual:

• cumpără produsul de la prima tarabă vizitată în continuare, cu atractivitatea $1$;
• cumpără produsul cu atractivitatea $5$ $(5 > 1)$.

Al doilea ritual este complet, deci satisfacția sa este $2$.

Ultimul vizitator parcurge tarabele cu produsele având atractivitatea $[9, 2, 6]$, cumpără primul produs, care are atractivitatea $9$ și apoi nu mai poate cumpăra nimic, deci nu finalizează complet niciun ritual. Satisfacția sa va fi $0$.