คุณมีความสามารถในการสร้างหุ่นยนต์ที่มีความสูงอยู่ในช่วง $[0, d]$ เพื่อทดสอบพวกมัน คุณได้สร้างเส้นทางความยาว $n$ ที่มีสิ่งกีดขวางบางส่วนอยู่ รายละเอียดของสิ่งกีดขวางถูกกำหนดให้เป็นอาเรย์ $a$ หาก $a_i = 0$ จะไม่มีสิ่งกีดขวางที่ตำแหน่งที่ $i$ มิฉะนั้นจะมีสิ่งกีดขวางที่มีความสูง $a_i > 0$
ในการทดสอบหุ่นยนต์ของคุณ คุณจะเลือกช่วง $[l, r]$ และปล่อยให้หุ่นยนต์วิ่งผ่านสิ่งกีดขวางทั้งหมดที่อยู่ในช่วงนั้น เมื่อหุ่นยนต์พบกับสิ่งกีดขวางที่มีค่า $a_i > 0$ จะเกิดเหตุการณ์ใดเหตุการณ์หนึ่งจากสองความเป็นไปได้ต่อไปนี้:
- หากความสูงปัจจุบันของหุ่นยนต์ $h$ น้อยกว่า $a_i$ จะไม่มีอะไรเกิดขึ้นเนื่องจากหุ่นยนต์เตี้ยเกินไปที่จะชนสิ่งกีดขวาง
- หากความสูงปัจจุบันของหุ่นยนต์ $h$ มีค่าอย่างน้อย $a_i$ ความสูงใหม่จะเปลี่ยนเป็น $h' = h - a_i$
ตอนนี้คุณต้องตอบคำถาม $q$ ข้อ สำหรับแต่ละช่วงใน $q$ ช่วง $[l_i, r_i]$ คุณต้องบอกความสูงที่เป็นไปได้มากที่สุดที่หุ่นยนต์จะเหลืออยู่หลังจากวิ่งผ่านสิ่งกีดขวางในช่วงนั้น หากเลือกความสูงเริ่มต้นจากช่วง $[0, d]$
ข้อมูลนำเข้า
บรรทัดแรกประกอบด้วยจำนวนเต็ม $n, q, d$ ($1 \le n, q \le 3 \cdot 10^5, 1 \le d \le 10^9$) — ความยาวของอาเรย์และจำนวนคำถาม
บรรทัดที่สองประกอบด้วยจำนวนเต็ม $n$ จำนวน $a_i$ ($0 \le a_i \le 10^9$) — รายละเอียดของอาเรย์
อีก $q$ บรรทัดถัดไปประกอบด้วยคู่ของจำนวนเต็ม $[l_i, r_i]$ ($1 \le l_i \le r_i \le n$) — รายละเอียดของคำถาม
ข้อมูลส่งออก
แสดงผลจำนวนเต็ม $q$ จำนวน — คำตอบของคำถาม
ตัวอย่าง
ข้อมูลนำเข้า 1
5 3 5 0 2 6 1 3 5 5 1 5 1 3
ข้อมูลส่งออก 1
2 2 3
ข้อมูลนำเข้า 2
7 5 10 7 6 2 5 0 1 4 1 3 1 7 4 7 2 5 4 6
ข้อมูลส่งออก 2
3 2 3 3 4