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