JOI Railways é uma empresa que opera uma linha ferroviária. Na linha da JOI Railways, há $N$ estações dispostas em linha reta, numeradas de $1$ a $N$. Para cada $i$ ($1 \le i \le N-1$), a estação $i$ e a estação $i+1$ estão ligadas por um troço de via férrea.

A JOI Railways tem $K$ tipos de comboios que circulam nos dois sentidos. Os tipos de comboios são representados por inteiros entre $1$ e $K$, inclusive. Cada estação tem um nível, que é um inteiro entre $1$ e $K$, inclusive. Para cada $i$ ($1 \le i \le N$), a estação $i$ tem nível $L_i$. As estações das duas extremidades, isto é, a estação $1$ e a estação $N$, têm nível $K$.

Um comboio do tipo $j$ ($1 \le j \le K$) para em todas as estações cujo nível é maior ou igual a $j$ e não para em nenhuma outra estação. Como as estações das duas extremidades, isto é, a estação $1$ e a estação $N$, têm nível $K$, todos os comboios param nessas estações.

Muitos passageiros utilizam a JOI Railways todos os dias. Durante a viagem, podem apanhar um comboio que siga no sentido oposto ao destino ou passar pelo destino. No fim da viagem, têm de parar no destino. Não gostam muito de parar nas estações. Por isso, tentam seguir um percurso com o menor número de paragens intermédias, independentemente do número de estações por onde passam sem parar ou do número de transbordos. Se um passageiro parar numa estação para mudar de comboio, isso conta como uma paragem. A primeira paragem na estação de partida e a última paragem no destino não são consideradas paragens intermédias.

A sua tarefa é escrever um programa que responda a consultas sobre o número mínimo de paragens intermédias para cada passageiro.

Tarefa

Dadas as informações sobre a linha ferroviária da JOI Railways e a estação de partida e o destino de cada passageiro, escreva um programa que responda a consultas sobre o número mínimo de paragens intermédias para cada passageiro.

Entrada

Leia os seguintes dados da entrada padrão.

• A primeira linha da entrada contém três inteiros separados por espaços, $N,K,Q$. Isto significa que a JOI Railways tem $N$ estações, existem $K$ tipos de comboios e são dadas $Q$ consultas sobre viagens entre duas estações.
• A $i$-ésima linha ($1 \le i \le N$) das $N$ linhas seguintes contém um inteiro $L_i$, o nível da estação $i$.
• A $k$-ésima linha ($1 \le k \le Q$) das $Q$ linhas seguintes contém dois inteiros separados por um espaço, $A_i,B_i$. Isto significa que a estação de partida e o destino do $k$-ésimo passageiro são as estações $A_i,B_i$, respetivamente.

Saída

Escreva $Q$ linhas na saída padrão. A $k$-ésima linha ($1 \le k \le Q$) da saída contém o número mínimo de paragens intermédias de um percurso da estação $A_k$ até à estação $B_k$.

Restrições

Todos os dados de entrada satisfazem as seguintes condições.

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

Subtarefas

Há 4 subtarefas. A pontuação e as restrições adicionais de cada subtarefa são as seguintes:

Subtarefa 1 [5 pontos]

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

Subtarefa 2 [15 pontos]

• $Q \le 50$.

Subtarefa 3 [25 pontos]

• $K \le 20$.

Subtarefa 4 [55 pontos]

Não há restrições adicionais.

Exemplos

Entrada 1

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

Saída 1

1
3
0

Explicação

Neste exemplo, são dadas três consultas sobre viagens entre duas estações.

• A primeira consulta diz respeito à viagem da estação $2$ até à estação $4$. Se um passageiro apanhar um comboio do tipo $1$ da estação $2$ até à estação $4$, há apenas uma paragem intermédia, a estação $3$.
• A segunda consulta diz respeito à viagem da estação $4$ até à estação $9$. Se um passageiro apanhar um comboio do tipo $1$ da estação $4$ até à estação $5$, depois um comboio do tipo $2$ da estação $5$ até à estação $1$ e, por fim, um comboio do tipo $3$ da estação $1$ até à estação $9$, há três paragens intermédias, as estações $5,1,8$.
• A terceira consulta diz respeito à viagem da estação $6$ até à estação $7$. Se um passageiro apanhar um comboio do tipo $2$ da estação $6$ até à estação $7$, não há paragens intermédias.

Entrada 2

5 2 1
2
1
1
1
2
1 4

Saída 2

1

Explicação

Note que os passageiros podem passar pelo destino durante a viagem.

Entrada 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

Saída 3

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