JOI Railways ist ein Unternehmen, das eine Eisenbahnstrecke betreibt. Auf dieser Strecke liegen $N$ Bahnhöfe auf einer geraden Linie, nummeriert von $1$ bis $N$. Für jedes $i$ ($1 \le i \le N-1$) sind Bahnhof $i$ und Bahnhof $i+1$ durch ein Gleis verbunden.

JOI Railways hat $K$ Zugtypen, die in beide Richtungen fahren. Die Zugtypen werden durch ganze Zahlen von $1$ bis einschließlich $K$ dargestellt. Jeder Bahnhof hat eine Stufe, die ebenfalls eine ganze Zahl von $1$ bis einschließlich $K$ ist. Für jedes $i$ ($1 \le i \le N$) hat Bahnhof $i$ die Stufe $L_i$. Die beiden Endbahnhöfe, also Bahnhof $1$ und Bahnhof $N$, haben die Stufe $K$.

Ein Zug vom Typ $j$ ($1 \le j \le K$) hält an jedem Bahnhof, dessen Stufe mindestens $j$ ist, und an keinem anderen Bahnhof. Da die beiden Endbahnhöfe, also Bahnhof $1$ und Bahnhof $N$, die Stufe $K$ haben, hält jeder Zug an diesen Bahnhöfen.

Jeden Tag nutzen viele Fahrgäste JOI Railways. Während ihrer Reise dürfen sie einen Zug nehmen, der in die dem Ziel entgegengesetzte Richtung fährt, oder am Ziel vorbeifahren. Am Ende der Reise müssen sie am Ziel halten. Sie halten nicht besonders gern an Bahnhöfen. Daher versuchen sie, eine Route mit möglichst wenigen Zwischenhalten zu nehmen, unabhängig von der Anzahl der durchfahrenen Bahnhöfe oder der Umstiege. Wenn ein Fahrgast an einem Bahnhof hält, um umzusteigen, zählt dies als ein Halt. Der erste Halt am Startbahnhof und der letzte Halt am Ziel gelten nicht als Zwischenhalte.

Deine Aufgabe ist es, ein Programm zu schreiben, das Anfragen zur minimalen Anzahl von Zwischenhalten für jeden Fahrgast beantwortet.

Aufgabe

Gegeben sind Informationen über die Eisenbahnstrecke von JOI Railways sowie Startbahnhof und Ziel jedes Fahrgasts. Schreibe ein Programm, das Anfragen zur minimalen Anzahl von Zwischenhalten für jeden Fahrgast beantwortet.

Eingabe

Lies die folgenden Daten von der Standardeingabe.

• Die erste Zeile enthält drei durch Leerzeichen getrennte ganze Zahlen $N,K,Q$. Dies bedeutet, dass JOI Railways $N$ Bahnhöfe und $K$ Zugtypen hat und $Q$ Anfragen zu Reisen zwischen zwei Bahnhöfen gegeben sind.
• Die $i$-te Zeile ($1 \le i \le N$) der folgenden $N$ Zeilen enthält eine ganze Zahl $L_i$, die Stufe von Bahnhof $i$.
• Die $k$-te Zeile ($1 \le k \le Q$) der folgenden $Q$ Zeilen enthält zwei durch ein Leerzeichen getrennte ganze Zahlen $A_i,B_i$. Dies bedeutet, dass Startbahnhof und Ziel des $k$-ten Fahrgasts die Bahnhöfe $A_i$ beziehungsweise $B_i$ sind.

Ausgabe

Schreibe $Q$ Zeilen auf die Standardausgabe. Die $k$-te Zeile ($1 \le k \le Q$) enthält die minimale Anzahl von Zwischenhalten auf einer Route von Bahnhof $A_k$ zu Bahnhof $B_k$.

Beschränkungen

Alle Eingabedaten erfüllen die folgenden Bedingungen.

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

Teilaufgaben

Es gibt 4 Teilaufgaben. Die Punktzahl und die zusätzlichen Beschränkungen jeder Teilaufgabe sind wie folgt:

Teilaufgabe 1 [5 Punkte]

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

Teilaufgabe 2 [15 Punkte]

• $Q \le 50$.

Teilaufgabe 3 [25 Punkte]

• $K \le 20$.

Teilaufgabe 4 [55 Punkte]

Es gibt keine zusätzlichen Beschränkungen.

Beispiele

Eingabe 1

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

Ausgabe 1

1
3
0

Hinweis

In dieser Beispieleingabe sind drei Anfragen zu Reisen zwischen zwei Bahnhöfen gegeben.

• Die erste Anfrage betrifft die Reise von Bahnhof $2$ zu Bahnhof $4$. Nimmt ein Fahrgast einen Zug vom Typ $1$ von Bahnhof $2$ zu Bahnhof $4$, gibt es nur einen Zwischenhalt, nämlich Bahnhof $3$.
• Die zweite Anfrage betrifft die Reise von Bahnhof $4$ zu Bahnhof $9$. Nimmt ein Fahrgast einen Zug vom Typ $1$ von Bahnhof $4$ zu Bahnhof $5$, dann einen Zug vom Typ $2$ von Bahnhof $5$ zu Bahnhof $1$ und schließlich einen Zug vom Typ $3$ von Bahnhof $1$ zu Bahnhof $9$, gibt es drei Zwischenhalte, nämlich die Bahnhöfe $5,1,8$.
• Die dritte Anfrage betrifft die Reise von Bahnhof $6$ zu Bahnhof $7$. Nimmt ein Fahrgast einen Zug vom Typ $2$ von Bahnhof $6$ zu Bahnhof $7$, gibt es keine Zwischenhalte.

Eingabe 2

5 2 1
2
1
1
1
2
1 4

Ausgabe 2

1

Hinweis

Beachte, dass Fahrgäste während ihrer Reise am Ziel vorbeifahren dürfen.

Eingabe 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

Ausgabe 3

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