JOI Railways es una empresa que opera una línea ferroviaria. En la línea de JOI Railways hay $N$ estaciones situadas en línea recta, numeradas del $1$ al $N$. Para cada $i$ ($1\le i\le N-1$), la estación $i$ y la estación $i+1$ están conectadas por una vía férrea.

JOI Railways tiene $K$ tipos de trenes que circulan en ambos sentidos. Los tipos de trenes se representan mediante enteros entre $1$ y $K$, inclusive. Cada estación tiene un nivel que es un entero entre $1$ y $K$, inclusive. Para cada $i$ ($1\le i\le N$), la estación $i$ tiene nivel $L_i$. Las estaciones de ambos extremos, es decir, la estación $1$ y la estación $N$, tienen nivel $K$.

Un tren de tipo $j$ ($1\le j\le K$) se detiene en todas las estaciones cuyo nivel es mayor o igual que $j$ y no se detiene en ninguna otra. Como las estaciones de ambos extremos, es decir, la estación $1$ y la estación $N$, tienen nivel $K$, todos los trenes se detienen en ellas.

Muchos pasajeros utilizan JOI Railways todos los días. Durante el viaje pueden tomar un tren que circule en sentido opuesto a su destino o pasar de largo por el destino. Al final del viaje deben detenerse en el destino. No les gusta mucho detenerse en las estaciones. Por ello, intentan tomar una ruta con el menor número de paradas intermedias, independientemente del número de estaciones por las que pasen o del número de transbordos. Si un pasajero se detiene en una estación para cambiar de tren, se cuenta como una parada. La primera parada en la estación de origen y la última parada en el destino no se consideran paradas intermedias.

Tu tarea es escribir un programa que responda consultas sobre el número mínimo de paradas intermedias de cada pasajero.

Tarea

Dada la información de la línea de JOI Railways y la estación de origen y el destino de cada pasajero, escribe un programa que responda consultas sobre el número mínimo de paradas intermedias de cada pasajero.

Entrada

Lee los siguientes datos de la entrada estándar.

• La primera línea de la entrada contiene tres enteros $N$, $K$, $Q$ separados por espacios. Indican que hay $N$ estaciones en JOI Railways, que hay $K$ tipos de trenes y que se dan $Q$ consultas sobre viajes entre dos estaciones.
• La línea $i$ ($1\le i\le N$) de las siguientes $N$ líneas contiene un entero $L_i$, el nivel de la estación $i$.
• La línea $k$ ($1\le k\le Q$) de las siguientes $Q$ líneas contiene dos enteros $A_i$, $B_i$ separados por un espacio. Indican que la estación de origen y el destino del pasajero $k$ son las estaciones $A_i$, $B_i$, respectivamente.

Salida

Escribe $Q$ líneas en la salida estándar. La línea $k$ ($1\le k\le Q$) de la salida contiene el número mínimo de paradas intermedias de una ruta desde la estación $A_k$ hasta la estación $B_k$.

Restricciones

Todos los datos de entrada satisfacen las siguientes condiciones.

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

Subtareas

Hay 4 subtareas. La puntuación y las restricciones adicionales de cada subtarea son las siguientes:

Subtarea 1 [5 puntos]

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

Subtarea 2 [15 puntos]

• $Q\le 50$.

Subtarea 3 [25 puntos]

• $K\le 20$.

Subtarea 4 [55 puntos]

No hay restricciones adicionales.

Ejemplos

Entrada 1

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

Salida 1

1
3
0

Nota

En esta entrada de ejemplo se dan tres consultas sobre viajes entre dos estaciones.

• La primera consulta trata del viaje desde la estación $2$ hasta la estación $4$. Si un pasajero toma un tren de tipo $1$ desde la estación $2$ hasta la estación $4$, solo hay una parada intermedia, la estación $3$.
• La segunda consulta trata del viaje desde la estación $4$ hasta la estación $9$. Si un pasajero toma un tren de tipo $1$ desde la estación $4$ hasta la estación $5$, después un tren de tipo $2$ desde la estación $5$ hasta la estación $1$ y, finalmente, un tren de tipo $3$ desde la estación $1$ hasta la estación $9$, hay tres paradas intermedias: las estaciones $5$, $1$, $8$.
• La tercera consulta trata del viaje desde la estación $6$ hasta la estación $7$. Si un pasajero toma un tren de tipo $2$ desde la estación $6$ hasta la estación $7$, no hay paradas intermedias.

Entrada 2

5 2 1
2
1
1
1
2
1 4

Salida 2

1

Nota

Ten en cuenta que los pasajeros pueden pasar de largo por el destino durante el viaje.

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

Salida 3

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