JOI Railways är ett företag som driver en järnväg. Längs JOI Railways järnväg ligger $N$ stationer på en rät linje, numrerade från $1$ till $N$. För varje $i$ ($1\le i\le N-1$) är station $i$ och station $i+1$ förbundna med ett järnvägsspår.

JOI Railways har $K$ typer av tåg som går i båda riktningarna. Tågtyperna uttrycks som heltal mellan $1$ och $K$, inklusive. Varje station har en nivå som är ett heltal mellan $1$ och $K$, inklusive. För varje $i$ ($1\le i\le N$) har station $i$ nivån $L_i$. Stationerna i båda ändarna, nämligen station $1$ och station $N$, har nivån $K$.

Ett tåg av typ $j$ ($1\le j\le K$) stannar vid varje station vars nivå är större än eller lika med $j$, och det stannar inte vid några andra stationer. Eftersom stationerna i båda ändarna, nämligen station $1$ och station $N$, har nivån $K$, stannar varje tåg vid dessa stationer.

Många passagerare reser med JOI Railways varje dag. Under resan kan de ta ett tåg vars riktning är motsatt destinationen, eller så kan de passera destinationen. I slutet av resan måste de stanna vid destinationen. De tycker inte särskilt mycket om att stanna vid stationer. Därför försöker de välja en resväg med minimalt antal mellanliggande stopp oavsett antalet passerade stationer eller antalet tågbyten. Om en passagerare stannar vid en station för att byta tåg räknar vi det som ett stopp. Det första stoppet vid startstationen och det sista stoppet vid destinationen räknas inte som mellanliggande stopp.

Din uppgift är att skriva ett program som besvarar frågor om det minimala antalet mellanliggande stopp för varje passagerare.

Uppgift

Givet information om JOI Railways järnväg samt startstationen och destinationen för varje passagerare, skriv ett program som besvarar frågor om det minimala antalet mellanliggande stopp för varje passagerare.

Indata

Läs följande data från standard inmatning.

• Den första raden i indata innehåller tre blankstegsseparerade heltal $N,K,Q$. Detta betyder att det finns $N$ stationer i JOI Railways, att det finns $K$ typer av tåg och att $Q$ frågor om resor mellan två stationer ges.
• Den $i$-te raden ($1\le i\le N$) av de följande $N$ raderna innehåller ett heltal $L_i$, nivån på station $i$.
• Den $k$-te raden ($1\le k\le Q$) av de följande $Q$ raderna innehåller två blankstegsseparerade heltal $A_i,B_i$. Detta betyder att startstationen och destinationen för den $k$-te passageraren är stationerna $A_i,B_i$.

Utdata

Skriv $Q$ rader till standard utmatning. Den $k$-te raden ($1\le k\le Q$) i utdata ska innehålla det minimala antalet mellanliggande stopp för en resväg från station $A_k$ till station $B_k$.

Begränsningar

All indata uppfyller följande villkor.

• $2\le N\le 100\,000$.
• $1\le K\le N$.
• $1\le Q\le 100\,000$.
• $1\le L_i\le K$ ($1\le i\le N$).
• $1\le A_k\le N$ ($1\le k\le Q$).
• $1\le B_k\le N$ ($1\le k\le Q$).
• $A_k\ne B_k$ ($1\le k\le Q$).

Deluppgifter

Det finns 4 deluppgifter. Poängen och de ytterligare begränsningarna för varje deluppgift är följande:

Deluppgift 1 [5 poäng]

• $N\le 100$.
• $K\le 100$.
• $Q\le 50$.

Deluppgift 2 [15 poäng]

• $Q\le 50$.

Deluppgift 3 [25 poäng]

• $K\le 20$.

Deluppgift 4 [55 poäng]

Det finns inga ytterligare begränsningar.

Exempel

Indata 1

9 3 3
3
1
1
1
2
2
2
3
3
2 4
4 9
6 7

Utdata 1

1
3
0

Förklaring

I detta exempel ges tre frågor om resor mellan två stationer.

• Den första frågan gäller resan från station $2$ till station $4$. Om en passagerare tar ett tåg av typ $1$ från station $2$ till station $4$ blir det bara ett mellanliggande stopp, station $3$.
• Den andra frågan gäller resan från station $4$ till station $9$. Om en passagerare tar ett tåg av typ $1$ från station $4$ till station $5$, sedan ett tåg av typ $2$ från station $5$ till station $1$, och slutligen ett tåg av typ $3$ från station $1$ till station $9$, blir det tre mellanliggande stopp, stationerna $5,1,8$.
• Den tredje frågan gäller resan från station $6$ till station $7$. Om en passagerare tar ett tåg av typ $2$ från station $6$ till station $7$ blir det inga mellanliggande stopp.

Indata 2

5 2 1
2
1
1
1
2
1 4

Utdata 2

1

Förklaring

Observera att passagerare kan passera destinationen under resan.

Indata 3

15 5 15
5
4
1
2
3
1
1
2
4
5
4
1
5
3
5
8 1
11 1
5 3
6 11
9 12
15 14
15 2
3 12
2 1
4 8
15 5
12 6
1 13
13 8
14 9

Utdata 3

2
1
1
3
2
0
3
4
0
1
3
4
1
2
2