JOI Railways adalah perusahaan yang mengoperasikan satu jalur kereta api. Pada jalur kereta api JOI Railways, terdapat $N$ stasiun pada sebuah garis lurus yang diberi nomor dari $1$ hingga $N$. Untuk setiap $i$ ($1 \le i \le N-1$), stasiun $i$ dan stasiun $i+1$ dihubungkan oleh rel kereta api.

JOI Railways memiliki $K$ jenis kereta yang berjalan dalam kedua arah. Jenis kereta dinyatakan dengan bilangan bulat dari $1$ hingga $K$, inklusif. Setiap stasiun memiliki tingkat berupa bilangan bulat dari $1$ hingga $K$, inklusif. Untuk setiap $i$ ($1 \le i \le N$), stasiun $i$ memiliki tingkat $L_i$. Kedua stasiun ujung, yaitu stasiun $1$ dan stasiun $N$, memiliki tingkat $K$.

Kereta jenis $j$ ($1 \le j \le K$) berhenti di setiap stasiun yang tingkatnya lebih besar atau sama dengan $j$, dan tidak berhenti di stasiun lainnya. Karena kedua stasiun ujung, yaitu stasiun $1$ dan stasiun $N$, memiliki tingkat $K$, setiap kereta berhenti di kedua stasiun tersebut.

Banyak penumpang menggunakan JOI Railways setiap hari. Selama perjalanan, mereka boleh naik kereta yang arahnya berlawanan dengan tujuan, atau melewati tujuan mereka. Pada akhir perjalanan, mereka harus berhenti di tujuan. Mereka tidak begitu suka berhenti di stasiun. Oleh karena itu, mereka berusaha memilih rute dengan jumlah perhentian antara sesedikit mungkin, tanpa memperhatikan jumlah stasiun yang dilewati atau jumlah pergantian kereta. Jika penumpang berhenti di sebuah stasiun untuk berganti kereta, hal itu dihitung sebagai satu perhentian. Perhentian pertama di stasiun awal dan perhentian terakhir di tujuan tidak dianggap sebagai perhentian antara.

Tugas Anda adalah menulis program yang menjawab pertanyaan tentang jumlah minimum perhentian antara untuk setiap penumpang.

Tugas

Dengan diberikan informasi jalur kereta api JOI Railways serta stasiun awal dan tujuan setiap penumpang, tulislah program yang menjawab pertanyaan tentang jumlah minimum perhentian antara untuk setiap penumpang.

Masukan

Bacalah data berikut dari masukan standar.

• Baris pertama masukan berisi tiga bilangan bulat $N$, $K$, $Q$ yang dipisahkan oleh spasi. Ini berarti JOI Railways memiliki $N$ stasiun, terdapat $K$ jenis kereta, dan diberikan $Q$ pertanyaan tentang perjalanan antara dua stasiun.
• Baris ke-$i$ ($1 \le i \le N$) dari $N$ baris berikutnya berisi sebuah bilangan bulat $L_i$, yaitu tingkat stasiun $i$.
• Baris ke-$k$ ($1 \le k \le Q$) dari $Q$ baris berikutnya berisi dua bilangan bulat $A_i$, $B_i$ yang dipisahkan oleh spasi. Ini berarti stasiun awal dan tujuan penumpang ke-$k$ adalah stasiun $A_i$, $B_i$, secara berurutan.

Keluaran

Tulislah $Q$ baris ke keluaran standar. Baris ke-$k$ ($1 \le k \le Q$) keluaran berisi jumlah minimum perhentian antara pada rute dari stasiun $A_k$ ke stasiun $B_k$.

Batasan

Semua data masukan memenuhi kondisi berikut.

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

Subsoal

Terdapat 4 subsoal. Nilai dan batasan tambahan untuk setiap subsoal adalah sebagai berikut:

Subsoal 1 [5 poin]

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

Subsoal 2 [15 poin]

• $Q \le 50$.

Subsoal 3 [25 poin]

• $K \le 20$.

Subsoal 4 [55 poin]

Tidak ada batasan tambahan.

Contoh

Masukan 1

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

Keluaran 1

1
3
0

Penjelasan

Dalam contoh masukan ini, diberikan tiga pertanyaan tentang perjalanan antara dua stasiun.

• Pertanyaan pertama membahas perjalanan dari stasiun $2$ ke stasiun $4$. Jika penumpang naik kereta jenis $1$ dari stasiun $2$ ke stasiun $4$, hanya ada satu perhentian antara, yaitu stasiun $3$.
• Pertanyaan kedua membahas perjalanan dari stasiun $4$ ke stasiun $9$. Jika penumpang naik kereta jenis $1$ dari stasiun $4$ ke stasiun $5$, lalu kereta jenis $2$ dari stasiun $5$ ke stasiun $1$, dan terakhir kereta jenis $3$ dari stasiun $1$ ke stasiun $9$, terdapat tiga perhentian antara, yaitu stasiun $5$, $1$, $8$.
• Pertanyaan ketiga membahas perjalanan dari stasiun $6$ ke stasiun $7$. Jika penumpang naik kereta jenis $2$ dari stasiun $6$ ke stasiun $7$, tidak ada perhentian antara.

Masukan 2

5 2 1
2
1
1
1
2
1 4

Keluaran 2

1

Penjelasan

Perhatikan bahwa penumpang boleh melewati tujuan selama perjalanan.

Masukan 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

Keluaran 3

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