JOI Railways er et selskap som driver én jernbane. Langs jernbanen til JOI Railways ligger det $N$ stasjoner på en rett linje, nummerert fra $1$ til $N$. For hver $i$ ($1\le i\le N-1$) er stasjon $i$ og stasjon $i+1$ forbundet med et jernbanespor.

JOI Railways har $K$ typer tog som går i begge retninger. Togtypene uttrykkes som heltall mellom $1$ og $K$, inkludert. Hver stasjon har et nivå som er et heltall mellom $1$ og $K$, inkludert. For hver $i$ ($1\le i\le N$) har stasjon $i$ nivå $L_i$. Stasjonene i begge ender, nemlig stasjon $1$ og stasjon $N$, har nivå $K$.

Et tog av type $j$ ($1\le j\le K$) stopper ved hver stasjon hvis nivå er større enn eller lik $j$, og det stopper ikke ved noen andre stasjoner. Siden stasjonene i begge ender, nemlig stasjon $1$ og stasjon $N$, har nivå $K$, stopper hvert tog ved disse stasjonene.

Mange passasjerer bruker JOI Railways hver dag. Under reisen kan de ta et tog som går i motsatt retning av destinasjonen, eller de kan passere destinasjonen. På slutten av reisen må de stoppe ved destinasjonen. De liker ikke særlig godt å stoppe ved stasjoner. Derfor prøver de å velge en rute med minimalt antall mellomstopp uavhengig av antallet passerte stasjoner eller antallet togbytter. Hvis en passasjer stopper ved en stasjon for å bytte tog, teller vi det som ett stopp. Det første stoppet ved startstasjonen og det siste stoppet ved destinasjonen regnes ikke som mellomstopp.

Din oppgave er å skrive et program som svarer på spørringer om det minimale antallet mellomstopp for hver passasjer.

Oppgave

Gitt informasjon om jernbanen til JOI Railways samt startstasjonen og destinasjonen til hver passasjer, skriv et program som svarer på spørringer om det minimale antallet mellomstopp for hver passasjer.

Inndata

Les følgende data fra standard inndata.

• Den første linjen i inndataene inneholder tre mellomromseparerte heltall $N,K,Q$. Dette betyr at det er $N$ stasjoner i JOI Railways, det er $K$ typer tog, og det gis $Q$ spørringer om reiser mellom to stasjoner.
• Den $i$-te linjen ($1\le i\le N$) av de følgende $N$ linjene inneholder et heltall $L_i$, nivået til stasjon $i$.
• Den $k$-te linjen ($1\le k\le Q$) av de følgende $Q$ linjene inneholder to mellomromseparerte heltall $A_i,B_i$. Dette betyr at startstasjonen og destinasjonen til den $k$-te passasjeren er henholdsvis stasjonene $A_i,B_i$.

Utdata

Skriv $Q$ linjer til standard utdata. Den $k$-te linjen ($1\le k\le Q$) i utdataene skal inneholde det minimale antallet mellomstopp på en rute fra stasjon $A_k$ til stasjon $B_k$.

Begrensninger

Alle inndata tilfredsstiller følgende betingelser.

• $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$).

Deloppgaver

Det er 4 deloppgaver. Poengsummen og tilleggsbegrensningene for hver deloppgave er som følger:

Deloppgave 1 [5 poeng]

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

Deloppgave 2 [15 poeng]

• $Q\le 50$.

Deloppgave 3 [25 poeng]

• $K\le 20$.

Deloppgave 4 [55 poeng]

Det er ingen ytterligere begrensninger.

Eksempler

Inndata 1

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

Utdata 1

1
3
0

Merk

I dette eksempelet gis det tre spørringer om reiser mellom to stasjoner.

• Den første spørringen gjelder reisen fra stasjon $2$ til stasjon $4$. Hvis en passasjer tar et tog av type $1$ fra stasjon $2$ til stasjon $4$, er det bare ett mellomstopp, stasjon $3$.
• Den andre spørringen gjelder reisen fra stasjon $4$ til stasjon $9$. Hvis en passasjer tar et tog av type $1$ fra stasjon $4$ til stasjon $5$, deretter et tog av type $2$ fra stasjon $5$ til stasjon $1$, og til slutt et tog av type $3$ fra stasjon $1$ til stasjon $9$, er det tre mellomstopp, stasjonene $5,1,8$.
• Den tredje spørringen gjelder reisen fra stasjon $6$ til stasjon $7$. Hvis en passasjer tar et tog av type $2$ fra stasjon $6$ til stasjon $7$, er det ingen mellomstopp.

Inndata 2

5 2 1
2
1
1
1
2
1 4

Utdata 2

1

Merk

Merk at passasjerer kan passere destinasjonen under reisen.

Inndata 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