คุณได้รับอาร์เรย์ $a$ ซึ่งประกอบด้วยจำนวนเต็มบวก $n$ ตัว อย่างไรก็ตาม สมาชิกบางตัวของ $a$ หายไป และถูกแทนที่ด้วยศูนย์
นิยามการแกว่งกวัด (oscillation) ของ $a$ บนช่วง $[\ell, r]$ ให้เท่ากับ $\max(a_\ell, \dots, a_r) - \min(a_\ell, \dots, a_r)$
คุณได้รับช่วง $q$ ช่วงในรูปแบบ $[\ell_i, r_i]$ จงแทนที่เลขศูนย์แต่ละตัวใน $a$ ด้วยจำนวนเต็มบวกเพื่อทำให้ผลรวมของการแกว่งกวัดของ $a$ บนช่วงทั้ง $q$ ช่วงมีค่าน้อยที่สุด
ข้อมูลนำเข้า
บรรทัดแรกประกอบด้วยจำนวนเต็มสองจำนวนคือ $n$ และ $q$ ($1 \le n, q \le 2 \cdot 10^5$)
บรรทัดที่สองประกอบด้วยจำนวนเต็ม $n$ จำนวนคือ $a_1, \dots, a_n$ ($0 \le a_i \le 10^9$) แทนสมาชิกของอาร์เรย์ ในที่นี้ $a_i = 0$ หมายความว่าสมาชิกตัวที่ $i$ หายไป
อีก $q$ บรรทัดถัดไปอธิบายช่วงต่างๆ แต่ละบรรทัดประกอบด้วยจำนวนเต็มสองจำนวนคือ $\ell_i$ และ $r_i$ ($1 \le \ell_i \le r_i \le n$)
ข้อมูลส่งออก
พิมพ์จำนวนเต็มเพียงตัวเดียว คือผลรวมของการแกว่งกวัดที่น้อยที่สุดของ $a$ บนช่วงที่กำหนดให้ทั้งหมด
ตัวอย่าง
ข้อมูลนำเข้า 1
5 2 2 1 0 3 2 1 3 3 5
ข้อมูลส่งออก 1
2
ข้อมูลนำเข้า 2
5 3 1 0 3 0 1 1 2 2 4 5 5
ข้อมูลส่งออก 2
2
ข้อมูลนำเข้า 3
7 4 4 4 0 1 0 3 4 1 3 1 3 3 5 4 7
ข้อมูลส่งออก 3
6
หมายเหตุ
ในตัวอย่างแรก อาร์เรย์ที่เหมาะสมที่สุดเพียงแบบเดียวคือ $a = [2, 1, 2, 3, 2]$
ในตัวอย่างที่สอง มีอาร์เรย์ที่เหมาะสมที่สุดหลายแบบ ตัวอย่างเช่น $a = [1, 2, 3, 2, 1]$ เป็นอาร์เรย์ที่เหมาะสมที่สุด
ในตัวอย่างที่สาม มีอาร์เรย์ที่เหมาะสมที่สุดหลายแบบ ตัวอย่างเช่น $a = [4, 4, 4, 1, 2, 3, 4]$ เป็นอาร์เรย์ที่เหมาะสมที่สุด