JOI Railways — компания, управляющая одной железной дорогой. На железной дороге JOI Railways расположены $N$ станций на одной прямой, пронумерованных от $1$ до $N$. Для каждого $i$ ($1 \le i \le N-1$) станции $i$ и $i+1$ соединены железнодорожным путём.

У JOI Railways есть $K$ типов поездов, курсирующих в обоих направлениях. Типы поездов обозначаются целыми числами от $1$ до $K$ включительно. У каждой станции есть уровень — целое число от $1$ до $K$ включительно. Для каждого $i$ ($1 \le i \le N$) станция $i$ имеет уровень $L_i$. Конечные станции, то есть станции $1$ и $N$, имеют уровень $K$.

Поезд типа $j$ ($1 \le j \le K$) останавливается на каждой станции, уровень которой не меньше $j$, и не останавливается ни на каких других станциях. Поскольку конечные станции $1$ и $N$ имеют уровень $K$, все поезда останавливаются на них.

Каждый день многие пассажиры пользуются JOI Railways. Во время поездки они могут ехать на поезде в сторону, противоположную пункту назначения, или проезжать пункт назначения без остановки. В конце поездки они должны остановиться в пункте назначения. Они не очень любят останавливаться на станциях. Поэтому они стараются выбрать маршрут с минимальным числом промежуточных остановок независимо от числа станций, проеханных без остановки, и числа пересадок. Если пассажир останавливается на станции для пересадки, это считается одной остановкой. Первая остановка на начальной станции и последняя остановка в пункте назначения не считаются промежуточными.

Ваша задача — написать программу, отвечающую на запросы о минимальном числе промежуточных остановок для каждого пассажира.

Задание

По информации о железной дороге JOI Railways, а также начальной станции и пункту назначения каждого пассажира напишите программу, отвечающую на запросы о минимальном числе промежуточных остановок для каждого пассажира.

Входные данные

Прочитайте следующие данные из стандартного ввода.

• Первая строка входных данных содержит три целых числа $N,K,Q$, разделённых пробелами. Это означает, что на железной дороге JOI Railways есть $N$ станций и $K$ типов поездов, а также даны $Q$ запросов о поездках между двумя станциями.
• $i$-я строка ($1 \le i \le N$) из следующих $N$ строк содержит целое число $L_i$ — уровень станции $i$.
• $k$-я строка ($1 \le k \le Q$) из следующих $Q$ строк содержит два целых числа $A_i,B_i$, разделённых пробелом. Это означает, что начальная станция и пункт назначения $k$-го пассажира — станции $A_i$ и $B_i$ соответственно.

Выходные данные

Выведите $Q$ строк в стандартный вывод. $k$-я строка ($1 \le k \le Q$) должна содержать минимальное число промежуточных остановок на маршруте от станции $A_k$ до станции $B_k$.

Ограничения

Все входные данные удовлетворяют следующим условиям.

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

Подзадачи

Есть 4 подзадачи. Баллы и дополнительные ограничения каждой подзадачи приведены ниже:

Подзадача 1 [5 баллов]

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

Подзадача 2 [15 баллов]

• $Q \le 50$.

Подзадача 3 [25 баллов]

• $K \le 20$.

Подзадача 4 [55 баллов]

Дополнительных ограничений нет.

Примеры

Входные данные 1

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

Выходные данные 1

1
3
0

Примечание

В этом примере даны три запроса о поездках между двумя станциями.

• Первый запрос относится к поездке от станции $2$ до станции $4$. Если пассажир едет на поезде типа $1$ от станции $2$ до станции $4$, будет лишь одна промежуточная остановка — станция $3$.
• Второй запрос относится к поездке от станции $4$ до станции $9$. Если пассажир едет на поезде типа $1$ от станции $4$ до станции $5$, затем на поезде типа $2$ от станции $5$ до станции $1$ и наконец на поезде типа $3$ от станции $1$ до станции $9$, будет три промежуточные остановки: станции $5,1,8$.
• Третий запрос относится к поездке от станции $6$ до станции $7$. Если пассажир едет на поезде типа $2$ от станции $6$ до станции $7$, промежуточных остановок не будет.

Входные данные 2

5 2 1
2
1
1
1
2
1 4

Выходные данные 2

1

Примечание

Обратите внимание, что во время поездки пассажиры могут проезжать пункт назначения без остановки.

Входные данные 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

Выходные данные 3

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