JOI Railways jest firmą obsługującą jedną linię kolejową. Na linii JOI Railways znajduje się $N$ stacji położonych na prostej, ponumerowanych od $1$ do $N$. Dla każdego $i$ ($1 \le i \le N-1$) stacje $i$ oraz $i+1$ są połączone torem kolejowym.

JOI Railways ma $K$ typów pociągów kursujących w obu kierunkach. Typy pociągów są oznaczone liczbami całkowitymi od $1$ do $K$ włącznie. Każda stacja ma poziom będący liczbą całkowitą od $1$ do $K$ włącznie. Dla każdego $i$ ($1 \le i \le N$) stacja $i$ ma poziom $L_i$. Stacje na obu końcach, czyli stacje $1$ i $N$, mają poziom $K$.

Pociąg typu $j$ ($1 \le j \le K$) zatrzymuje się na każdej stacji, której poziom jest większy lub równy $j$, i nie zatrzymuje się na żadnej innej stacji. Ponieważ stacje na obu końcach, czyli stacje $1$ i $N$, mają poziom $K$, każdy pociąg zatrzymuje się na tych stacjach.

Każdego dnia wielu pasażerów korzysta z JOI Railways. Podczas podróży mogą jechać pociągiem w kierunku przeciwnym do celu lub przejechać przez stację docelową. Na końcu podróży muszą zatrzymać się na stacji docelowej. Nie lubią zbytnio zatrzymywać się na stacjach. Dlatego wybierają trasę z najmniejszą liczbą postojów pośrednich, niezależnie od liczby mijanych stacji i liczby przesiadek. Jeśli pasażer zatrzymuje się na stacji, aby zmienić pociąg, liczymy to jako jeden postój. Pierwszy postój na stacji początkowej i ostatni postój na stacji docelowej nie są uznawane za postoje pośrednie.

Twoim zadaniem jest napisanie programu, który odpowie na zapytania o najmniejszą liczbę postojów pośrednich dla każdego pasażera.

Zadanie

Mając informacje o linii kolejowej JOI Railways oraz stację początkową i docelową każdego pasażera, napisz program odpowiadający na zapytania o najmniejszą liczbę postojów pośrednich dla każdego pasażera.

Wejście

Wczytaj następujące dane ze standardowego wejścia.

• Pierwszy wiersz wejścia zawiera trzy liczby całkowite $N$, $K$, $Q$ oddzielone spacjami. Oznacza to, że w JOI Railways jest $N$ stacji, istnieje $K$ typów pociągów i podano $Q$ zapytań dotyczących podróży między dwiema stacjami.
• $i$-ty wiersz ($1 \le i \le N$) spośród kolejnych $N$ wierszy zawiera liczbę całkowitą $L_i$, poziom stacji $i$.
• $k$-ty wiersz ($1 \le k \le Q$) spośród kolejnych $Q$ wierszy zawiera dwie liczby całkowite $A_i$, $B_i$ oddzielone spacją. Oznacza to, że stacją początkową i docelową $k$-tego pasażera są odpowiednio stacje $A_i$ i $B_i$.

Wyjście

Wypisz $Q$ wierszy na standardowe wyjście. $k$-ty wiersz ($1 \le k \le Q$) wyjścia zawiera najmniejszą liczbę postojów pośrednich na trasie ze stacji $A_k$ do stacji $B_k$.

Ograniczenia

Wszystkie dane wejściowe spełniają następujące warunki.

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

Podzadania

Są 4 podzadania. Punktacja i dodatkowe ograniczenia każdego podzadania są następujące:

Podzadanie 1 [5 punktów]

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

Podzadanie 2 [15 punktów]

• $Q \le 50$.

Podzadanie 3 [25 punktów]

• $K \le 20$.

Podzadanie 4 [55 punktów]

Brak dodatkowych ograniczeń.

Przykład

Wejście 1

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

Wyjście 1

1
3
0

Uwagi

W tym przykładzie podano trzy zapytania dotyczące podróży między dwiema stacjami.

• Pierwsze zapytanie dotyczy podróży ze stacji $2$ do stacji $4$. Jeśli pasażer pojedzie pociągiem typu $1$ ze stacji $2$ do stacji $4$, będzie tylko jeden postój pośredni, na stacji $3$.
• Drugie zapytanie dotyczy podróży ze stacji $4$ do stacji $9$. Jeśli pasażer pojedzie pociągiem typu $1$ ze stacji $4$ do stacji $5$, następnie pociągiem typu $2$ ze stacji $5$ do stacji $1$, a na końcu pociągiem typu $3$ ze stacji $1$ do stacji $9$, będą trzy postoje pośrednie, na stacjach $5$, $1$, $8$.
• Trzecie zapytanie dotyczy podróży ze stacji $6$ do stacji $7$. Jeśli pasażer pojedzie pociągiem typu $2$ ze stacji $6$ do stacji $7$, nie będzie żadnych postojów pośrednich.

Wejście 2

5 2 1
2
1
1
1
2
1 4

Wyjście 2

1

Uwagi

Zauważ, że pasażerowie mogą przejechać przez stację docelową w trakcie podróży.

Wejście 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

Wyjście 3

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