JOI Railways on yhtä rautatietä liikennöivä yhtiö. JOI Railwaysin rautatiellä on suoralla linjalla $N$ asemaa, jotka on numeroitu luvuilla $1$:stä $N$:ään. Jokaisella $i$ ($1\le i\le N-1$) asema $i$ ja asema $i+1$ on yhdistetty junaraiteella.

JOI Railwaysilla on $K$ junatyyppiä, jotka kulkevat molempiin suuntiin. Junatyypit ilmaistaan kokonaislukuina väliltä $1$ ja $K$, rajat mukaan lukien. Jokaisella asemalla on taso, joka on kokonaisluku väliltä $1$ ja $K$, rajat mukaan lukien. Jokaisella $i$ ($1\le i\le N$) aseman $i$ taso on $L_i$. Molemmissa päissä olevien asemien, eli aseman $1$ ja aseman $N$, taso on $K$.

Tyypin $j$ ($1\le j\le K$) juna pysähtyy jokaisella asemalla, jonka taso on suurempi tai yhtä suuri kuin $j$, eikä se pysähdy millään muulla asemalla. Koska molemmissa päissä olevien asemien, eli aseman $1$ ja aseman $N$, taso on $K$, jokainen juna pysähtyy näillä asemilla.

Monet matkustajat käyttävät JOI Railwaysia päivittäin. Matkan aikana he voivat ottaa junan, jonka kulkusuunta on määränpäähän nähden vastakkainen, tai he voivat ohittaa määränpään. Matkan päätteeksi heidän on pysähdyttävä määränpäässä. He eivät juurikaan pidä asemilla pysähtymisestä. Siksi he pyrkivät valitsemaan reitin, jolla välipysähdysten lukumäärä on mahdollisimman pieni riippumatta ohitettujen asemien tai junanvaihtojen lukumäärästä. Jos matkustaja pysähtyy asemalla vaihtaakseen junaa, se lasketaan yhdeksi pysähdykseksi. Ensimmäistä pysähdystä lähtöasemalla ja viimeistä pysähdystä määränpäässä ei lasketa välipysähdyksiksi.

Tehtäväsi on kirjoittaa ohjelma, joka vastaa kyselyihin kunkin matkustajan pienimmästä mahdollisesta välipysähdysten lukumäärästä.

Tehtävä

Kun annetaan tiedot JOI Railwaysin rautatiestä sekä kunkin matkustajan lähtöasemasta ja määränpäästä, kirjoita ohjelma, joka vastaa kyselyihin kunkin matkustajan pienimmästä mahdollisesta välipysähdysten lukumäärästä.

Syöte

Lue seuraavat tiedot standardisyötteestä.

• Syötteen ensimmäisellä rivillä on kolme välilyönnein erotettua kokonaislukua $N,K,Q$. Tämä tarkoittaa, että JOI Railwaysilla on $N$ asemaa, junatyyppejä on $K$ ja kahden aseman välisiä matkoja koskevia kyselyitä on $Q$.
• Seuraavista $N$ rivistä $i$:nnellä rivillä ($1\le i\le N$) on kokonaisluku $L_i$, aseman $i$ taso.
• Seuraavista $Q$ rivistä $k$:nnella rivillä ($1\le k\le Q$) on kaksi välilyönnillä erotettua kokonaislukua $A_i,B_i$. Tämä tarkoittaa, että $k$:nnen matkustajan lähtöasema ja määränpää ovat vastaavasti asemat $A_i,B_i$.

Tuloste

Tulosta standarditulosteeseen $Q$ riviä. Tulosteen $k$:nnella rivillä ($1\le k\le Q$) tulee olla pienin mahdollinen välipysähdysten lukumäärä reitillä asemalta $A_k$ asemalle $B_k$.

Rajoitukset

Kaikki syötetiedot täyttävät seuraavat ehdot.

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

Osatehtävät

Tehtävässä on 4 osatehtävää. Kunkin osatehtävän pistemäärä ja lisärajoitukset ovat seuraavat:

Osatehtävä 1 [5 pistettä]

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

Osatehtävä 2 [15 pistettä]

• $Q\le 50$.

Osatehtävä 3 [25 pistettä]

• $K\le 20$.

Osatehtävä 4 [55 pistettä]

Ei ole lisärajoituksia.

Esimerkit

Syöte 1

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

Tuloste 1

1
3
0

Huomautus

Tässä esimerkkisyötteessä annetaan kolme kyselyä kahden aseman välisistä matkoista.

• Ensimmäinen kysely koskee matkaa asemalta $2$ asemalle $4$. Jos matkustaja ottaa tyypin $1$ junan asemalta $2$ asemalle $4$, välipysähdyksiä on vain yksi, asema $3$.
• Toinen kysely koskee matkaa asemalta $4$ asemalle $9$. Jos matkustaja ottaa tyypin $1$ junan asemalta $4$ asemalle $5$, sitten tyypin $2$ junan asemalta $5$ asemalle $1$ ja lopuksi tyypin $3$ junan asemalta $1$ asemalle $9$, välipysähdyksiä on kolme: asemat $5,1,8$.
• Kolmas kysely koskee matkaa asemalta $6$ asemalle $7$. Jos matkustaja ottaa tyypin $2$ junan asemalta $6$ asemalle $7$, välipysähdyksiä ei ole lainkaan.

Syöte 2

5 2 1
2
1
1
1
2
1 4

Tuloste 2

1

Huomautus

Huomaa, että matkustajat voivat ohittaa määränpään matkan aikana.

Syöte 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

Tuloste 3

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