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