ให้ $B$ เป็นอาร์เรย์ที่มีความยาว $M$ คะแนน (score) ของ $B$ คือจำนวนของดัชนี $i$ ($2 \le i \le M - 1$) ที่มีดัชนี $x$ และ $y$ ซึ่งทำให้ $1 \le x < i < y \le M$ และ $2 \cdot B_i > B_x + B_y$

คุณได้รับอาร์เรย์ $A$ ที่มีความยาว $N$

คุณต้องตอบคำถาม $Q$ ข้อ

สำหรับแต่ละคำถาม $L$ $R$ ($1 \le L < R \le N, R - L + 1 \ge 3$) จงหาค่าของ:

$$\sum_{i=L}^{R-2} \sum_{j=i+2}^{R} \text{score}(A_i, A_{i+1}, \dots, A_j)$$

กล่าวอีกนัยหนึ่งคือ จงหาผลรวมของคะแนนของอาร์เรย์ย่อยทั้งหมดที่มีความยาวอย่างน้อย $3$ ซึ่งอยู่ภายใน $A_L, A_{L+1}, \dots, A_R$ อย่างสมบูรณ์

ข้อมูลนำเข้า

ข้อมูลนำเข้ามีรูปแบบดังต่อไปนี้:

T
N Q
A_1 A_2 ... A_N
L_1 R_1
:
L_Q R_Q

ข้อจำกัด

• ค่าข้อมูลนำเข้าทั้งหมดเป็นจำนวนเต็ม
• $1 \le T \le 10^4$
• $3 \le N \le 5 \times 10^5$
• $1 \le Q \le 5 \times 10^5$
• $1 \le L < R \le N$ และ $R - L + 1 \ge 3$
• รับประกันว่าผลรวมของ $N$ ในทุกชุดทดสอบจะไม่เกิน $5 \times 10^5$
• รับประกันว่าผลรวมของ $Q$ ในทุกชุดทดสอบจะไม่เกิน $5 \times 10^5$

ข้อมูลส่งออก

สำหรับแต่ละคำถาม ให้พิมพ์จำนวนเต็มหนึ่งจำนวน: ผลรวมของคะแนนของอาร์เรย์ย่อยทั้งหมดที่มีความยาวอย่างน้อย $3$ ซึ่งอยู่ภายใน $A_L, A_{L+1}, \dots, A_R$ อย่างสมบูรณ์

ตัวอย่าง

ข้อมูลนำเข้า 1

1
5 4
2 5 1 3 4
1 5
2 5
1 4
3 5

ข้อมูลส่งออก 1

6
2
2
1

หมายเหตุ

ชุดทดสอบที่ 1: สำหรับคำถาม $[1, 5]$ อาร์เรย์ย่อยที่มีความยาวอย่างน้อย $3$ ได้แก่:

• $[2, 5, 1]$, คะแนน $= 1$
• $[5, 1, 3]$, คะแนน $= 0$
• $[1, 3, 4]$, คะแนน $= 1$
• $[2, 5, 1, 3]$, คะแนน $= 1$
• $[5, 1, 3, 4]$, คะแนน $= 1$
• $[2, 5, 1, 3, 4]$, คะแนน $= 2$

ดังนั้น คำตอบคือ $6$