Låt $B$ vara en array med längden $M$. Poängen (score) för $B$ är antalet index $i$ ($2 \le i \le M - 1$) sådana att det finns index $x$ och $y$ med $1 \le x < i < y \le M$ och $2 \cdot B_i > B_x + B_y$.

Du får en array $A$ med längden $N$.

Du ska svara på $Q$ frågor.

För varje fråga $L$ $R$ ($1 \le L < R \le N, R - L + 1 \ge 3$), beräkna:

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

Med andra ord, hitta summan av poängen över alla delarrayer med längd minst $3$ som är helt inneslutna i $A_L, A_{L+1}, \dots, A_R$.

Indata

Indata ges i följande format:

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

Begränsningar

• Alla indatavärden är heltal.
• $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$ och $R - L + 1 \ge 3$.
• Det garanteras att summan av $N$ över alla testfall inte överstiger $5 \times 10^5$.
• Det garanteras att summan av $Q$ över alla testfall inte överstiger $5 \times 10^5$.

Utdata

För varje fråga, skriv ut ett enda heltal: summan av poängen över alla delarrayer med längd minst $3$ som är helt inneslutna i $A_L, A_{L+1}, \dots, A_R$.

Exempel

Indata 1

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

Utdata 1

6
2
2
1

Förklaring

Testfall 1: För frågan $[1, 5]$ är delarrayerna med längd minst $3$:

• $[2, 5, 1]$, poäng $= 1$
• $[5, 1, 3]$, poäng $= 0$
• $[1, 3, 4]$, poäng $= 1$
• $[2, 5, 1, 3]$, poäng $= 1$
• $[5, 1, 3, 4]$, poäng $= 1$
• $[2, 5, 1, 3, 4]$, poäng $= 2$

Alltså är svaret $6$.