יהי $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$.