JOI Railways er fyrirtæki sem rekur eina járnbraut. Á járnbraut JOI Railways eru $N$ stöðvar á beinni línu sem eru númeraðar frá $1$ til $N$. Fyrir hvert $i$ ($1\le i\le N-1$) eru stöð $i$ og stöð $i+1$ tengdar saman með járnbrautarteinum.

JOI Railways á $K$ tegundir af lestum sem ganga í báðar áttir. Tegundir lesta eru táknaðar sem heiltölur á milli $1$ og $K$, báðar meðtaldar. Hver stöð hefur stig sem er heiltala á milli $1$ og $K$, báðar meðtaldar. Fyrir hvert $i$ ($1\le i\le N$) hefur stöð $i$ stigið $L_i$. Stöðvarnar á báðum endum, þ.e. stöð $1$ og stöð $N$, hafa stigið $K$.

Lest af tegund $j$ ($1\le j\le K$) stoppar á hverri stöð þar sem stigið er stærra en eða jafnt og $j$, og hún stoppar ekki á neinum öðrum stöðvum. Þar sem stöðvarnar á báðum endum, þ.e. stöð $1$ og stöð $N$, hafa stigið $K$, stoppar sérhver lest á þessum stöðvum.

Margir farþegar nota JOI Railways á hverjum degi. Á ferðalagi geta þeir tekið lest sem fer í öfuga átt við áfangastaðinn, eða þeir geta farið fram hjá áfangastaðnum. Í lok ferðarinnar verða þeir að stoppa á áfangastaðnum. Þeim líkar ekki mjög vel að stoppa á stöðvum. Þess vegna reyna þeir að velja leið með lágmarksfjölda millistoppa óháð fjölda stöðva sem farið er fram hjá eða fjölda lestaraskipta. Ef farþegi stoppar á stöð til að skipta um lest teljum við það sem eitt stopp. Fyrsta stoppið á upphafsstöðinni og síðasta stoppið á áfangastaðnum teljast ekki sem millistopp.

Verkefni þitt er að skrifa forrit sem svarar fyrirspurnum um lágmarksfjölda millistoppa fyrir hvern farþega.

Verkefni

Með hliðsjón af upplýsingum um járnbraut JOI Railways og upphafsstöð og áfangastað hvers farþega, skrifið forrit sem svarar fyrirspurnum um lágmarksfjölda millistoppa fyrir hvern farþega.

Inntak

Lesið eftirfarandi gögn af staðalinntaki.

• Fyrsta línan í inntakinu inniheldur þrjár heiltölur $N,K,Q$ aðskildar með bili. Þetta þýðir að það eru $N$ stöðvar hjá JOI Railways, það eru $K$ tegundir af lestum og gefnar eru $Q$ fyrirspurnir um ferðir á milli tveggja stöðva.
• $i$-ta línan ($1\le i\le N$) af næstu $N$ línum inniheldur heiltölu $L_i$, stig stöðvar $i$.
• $k$-ta línan ($1\le k\le Q$) af næstu $Q$ línum inniheldur tvær heiltölur $A_i,B_i$ aðskildar með bili. Þetta þýðir að upphafsstöðin og áfangastaðurinn hjá $k$-ta farþeganum eru stöðvarnar $A_i,B_i$, í þessari röð.

Úttak

Skrifið $Q$ línur á staðalúttak. $k$-ta línan ($1\le k\le Q$) í úttakinu á að innihalda lágmarksfjölda millistoppa á leið frá stöð $A_k$ til stöðvar $B_k$.

Takmarkanir

Öll inntaksgögn uppfylla eftirfarandi skilyrði.

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

Undirverkefni

Það eru 4 undirverkefni. Stigafjöldi og viðbótartakmarkanir hvers undirverkefnis eru sem hér segir:

Undirverkefni 1 [5 stig]

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

Undirverkefni 2 [15 stig]

• $Q\le 50$.

Undirverkefni 3 [25 stig]

• $K\le 20$.

Undirverkefni 4 [55 stig]

Engar frekari takmarkanir.

Dæmi

Inntak 1

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

Úttak 1

1
3
0

Athugasemd

Í þessu sýnisinntaki eru gefnar þrjár fyrirspurnir um ferðir á milli tveggja stöðva.

• Fyrsta fyrirspurnin snýst um ferðina frá stöð $2$ til stöðvar $4$. Ef farþegi tekur lest af tegund $1$ frá stöð $2$ til stöðvar $4$ er aðeins eitt millistopp, stöð $3$.
• Önnur fyrirspurnin snýst um ferðina frá stöð $4$ til stöðvar $9$. Ef farþegi tekur lest af tegund $1$ frá stöð $4$ til stöðvar $5$, síðan lest af tegund $2$ frá stöð $5$ til stöðvar $1$ og loks lest af tegund $3$ frá stöð $1$ til stöðvar $9$, þá eru þrjú millistopp, stöðvarnar $5,1,8$.
• Þriðja fyrirspurnin snýst um ferðina frá stöð $6$ til stöðvar $7$. Ef farþegi tekur lest af tegund $2$ frá stöð $6$ til stöðvar $7$ eru engin millistopp.

Inntak 2

5 2 1
2
1
1
1
2
1 4

Úttak 2

1

Athugasemd

Athugið að farþegar geta farið fram hjá áfangastaðnum á ferðalaginu.

Inntak 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

Úttak 3

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