JOI Railways est une entreprise qui exploite une ligne ferroviaire. Sur cette ligne, $N$ gares sont disposées en ligne droite et numérotées de $1$ à $N$. Pour chaque $i$ ($1 \le i \le N-1$), les gares $i$ et $i+1$ sont reliées par une voie ferrée.

JOI Railways possède $K$ types de trains circulant dans les deux sens. Les types de trains sont représentés par des entiers compris entre $1$ et $K$, bornes incluses. Chaque gare possède un niveau, qui est un entier compris entre $1$ et $K$, bornes incluses. Pour chaque $i$ ($1 \le i \le N$), la gare $i$ a pour niveau $L_i$. Les gares aux deux extrémités, c'est-à-dire les gares $1$ et $N$, ont le niveau $K$.

Un train de type $j$ ($1 \le j \le K$) s'arrête à toutes les gares dont le niveau est supérieur ou égal à $j$, et ne s'arrête à aucune autre gare. Comme les gares aux deux extrémités, c'est-à-dire les gares $1$ et $N$, ont le niveau $K$, tous les trains s'y arrêtent.

De nombreux passagers utilisent JOI Railways chaque jour. Pendant leur trajet, ils peuvent prendre un train allant dans la direction opposée à leur destination, ou dépasser leur destination. À la fin du trajet, ils doivent s'arrêter à leur destination. Ils n'aiment pas beaucoup s'arrêter aux gares. Ils cherchent donc un itinéraire ayant le nombre minimal d'arrêts intermédiaires, indépendamment du nombre de gares traversées sans arrêt ou du nombre de correspondances. Si un passager s'arrête à une gare pour changer de train, cela compte comme un arrêt. L'arrêt initial à la gare de départ et l'arrêt final à la destination ne sont pas considérés comme des arrêts intermédiaires.

Votre tâche consiste à écrire un programme qui répond aux requêtes portant sur le nombre minimal d'arrêts intermédiaires pour chaque passager.

Tâche

Étant donnés les renseignements sur la ligne de JOI Railways ainsi que la gare de départ et la destination de chaque passager, écrivez un programme qui répond aux requêtes portant sur le nombre minimal d'arrêts intermédiaires pour chaque passager.

Entrée

Lisez les données suivantes sur l'entrée standard.

• La première ligne contient trois entiers séparés par des espaces : $N,K,Q$. Cela signifie que JOI Railways comporte $N$ gares et $K$ types de trains, et que $Q$ requêtes concernant des trajets entre deux gares sont données.
• La $i$-ème ligne ($1 \le i \le N$) parmi les $N$ lignes suivantes contient un entier $L_i$, le niveau de la gare $i$.
• La $k$-ème ligne ($1 \le k \le Q$) parmi les $Q$ lignes suivantes contient deux entiers séparés par un espace, $A_i,B_i$. Cela signifie que la gare de départ et la destination du $k$-ème passager sont respectivement les gares $A_i,B_i$.

Sortie

Écrivez $Q$ lignes sur la sortie standard. La $k$-ème ligne ($1 \le k \le Q$) contient le nombre minimal d'arrêts intermédiaires d'un itinéraire allant de la gare $A_k$ à la gare $B_k$.

Contraintes

Toutes les données d'entrée respectent les conditions suivantes.

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

Sous-tâches

Il y a 4 sous-tâches. Le score et les contraintes supplémentaires de chacune sont les suivants :

Sous-tâche 1 [5 points]

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

Sous-tâche 2 [15 points]

• $Q \le 50$.

Sous-tâche 3 [25 points]

• $K \le 20$.

Sous-tâche 4 [55 points]

Il n'y a aucune contrainte supplémentaire.

Exemples

Entrée 1

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

Sortie 1

1
3
0

Remarque

Dans cet exemple, trois requêtes concernant des trajets entre deux gares sont données.

• La première requête concerne le trajet de la gare $2$ à la gare $4$. Si un passager prend un train de type $1$ de la gare $2$ à la gare $4$, il n'y a qu'un arrêt intermédiaire, à la gare $3$.
• La deuxième requête concerne le trajet de la gare $4$ à la gare $9$. Si un passager prend un train de type $1$ de la gare $4$ à la gare $5$, puis un train de type $2$ de la gare $5$ à la gare $1$, et enfin un train de type $3$ de la gare $1$ à la gare $9$, il y a trois arrêts intermédiaires, aux gares $5,1,8$.
• La troisième requête concerne le trajet de la gare $6$ à la gare $7$. Si un passager prend un train de type $2$ de la gare $6$ à la gare $7$, il n'y a aucun arrêt intermédiaire.

Entrée 2

5 2 1
2
1
1
1
2
1 4

Sortie 2

1

Remarque

Notez que les passagers peuvent dépasser leur destination pendant le trajet.

Entrée 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

Sortie 3

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