JOI Railways è una compagnia che gestisce una linea ferroviaria. Sulla linea ferroviaria di JOI Railways ci sono $N$ stazioni disposte lungo una linea retta, numerate da $1$ a $N$. Per ogni $i$ ($1\le i\le N-1$), la stazione $i$ e la stazione $i+1$ sono collegate da un binario ferroviario.

JOI Railways dispone di $K$ tipi di treni che viaggiano in entrambe le direzioni. I tipi di treni sono espressi come interi compresi tra $1$ e $K$ inclusi. Ogni stazione ha un livello che è un intero compreso tra $1$ e $K$ inclusi. Per ogni $i$ ($1\le i\le N$), la stazione $i$ ha livello $L_i$. Le stazioni ad entrambe le estremità, ovvero la stazione $1$ e la stazione $N$, hanno livello $K$.

Un treno di tipo $j$ ($1\le j\le K$) ferma in ogni stazione il cui livello è maggiore o uguale a $j$, e non ferma in nessun'altra stazione. Poiché le stazioni ad entrambe le estremità, ovvero la stazione $1$ e la stazione $N$, hanno livello $K$, ogni treno ferma in queste stazioni.

Molti passeggeri utilizzano JOI Railways ogni giorno. Durante il viaggio, possono prendere un treno la cui direzione è opposta rispetto alla destinazione, oppure possono oltrepassare la destinazione. Alla fine del viaggio, devono fermarsi alla destinazione. Ai passeggeri non piace molto fermarsi nelle stazioni. Pertanto cercano di seguire un percorso con il numero minimo di fermate intermedie, indipendentemente dal numero di stazioni attraversate o dal numero di cambi. Se un passeggero si ferma in una stazione per cambiare treno, questa conta come una fermata. La prima fermata alla stazione di partenza e l'ultima fermata alla destinazione non sono considerate fermate intermedie.

Il tuo compito è scrivere un programma che risponda alle query sul numero minimo di fermate intermedie per ciascun passeggero.

Compito

Date le informazioni sulla ferrovia di JOI Railways e la stazione di partenza e la destinazione di ciascun passeggero, scrivi un programma che risponda alle query sul numero minimo di fermate intermedie per ciascun passeggero.

Formato di input

Leggi i seguenti dati dallo standard input.

• La prima riga di input contiene tre interi separati da spazi $N,K,Q$. Ciò significa che ci sono $N$ stazioni in JOI Railways, ci sono $K$ tipi di treni e vengono fornite $Q$ query riguardanti viaggi tra due stazioni.
• La $i$-esima riga ($1\le i\le N$) delle seguenti $N$ righe contiene un intero $L_i$, il livello della stazione $i$.
• La $k$-esima riga ($1\le k\le Q$) delle seguenti $Q$ righe contiene due interi separati da spazi $A_i,B_i$. Ciò significa che la stazione di partenza e la destinazione del $k$-esimo passeggero sono rispettivamente le stazioni $A_i,B_i$.

Formato di output

Scrivi $Q$ righe sullo standard output. La $k$-esima riga ($1\le k\le Q$) di output contiene il numero minimo di fermate intermedie di un percorso dalla stazione $A_k$ alla stazione $B_k$.

Vincoli

Tutti i dati di input soddisfano le seguenti condizioni.

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

Subtask

Ci sono 4 subtask. Il punteggio e i vincoli aggiuntivi di ciascun subtask sono i seguenti:

Subtask 1 [5 punti]

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

Subtask 2 [15 punti]

• $Q\le 50$.

Subtask 3 [25 punti]

• $K\le 20$.

Subtask 4 [55 punti]

Non ci sono vincoli aggiuntivi.

Esempi

Input 1

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

Output 1

1
3
0

Note

In questo input di esempio vengono fornite tre query riguardanti viaggi tra due stazioni.

• La prima query riguarda il viaggio dalla stazione $2$ alla stazione $4$. Se un passeggero prende un treno di tipo $1$ dalla stazione $2$ alla stazione $4$, c'è solo una fermata intermedia, la stazione $3$.
• La seconda query riguarda il viaggio dalla stazione $4$ alla stazione $9$. Se un passeggero prende un treno di tipo $1$ dalla stazione $4$ alla stazione $5$, poi un treno di tipo $2$ dalla stazione $5$ alla stazione $1$, e infine un treno di tipo $3$ dalla stazione $1$ alla stazione $9$, ci sono tre fermate intermedie, le stazioni $5,1,8$.
• La terza query riguarda il viaggio dalla stazione $6$ alla stazione $7$. Se un passeggero prende un treno di tipo $2$ dalla stazione $6$ alla stazione $7$, non ci sono fermate intermedie.

Input 2

5 2 1
2
1
1
1
2
1 4

Output 2

1

Note

Nota che i passeggeri possono oltrepassare la destinazione durante il viaggio.

Input 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

Output 3

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