لتكن $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$.