La $B$ være en tabell med lengde $M$. Poengsummen (score) til $B$ er antallet indekser $i$ ($2 \le i \le M - 1$) slik at det finnes indekser $x$ og $y$ med $1 \le x < i < y \le M$ og $2 \cdot B_i > B_x + B_y$.

Du får oppgitt en tabell $A$ med lengde $N$.

Du må svare på $Q$ spørringer.

For hver spørring $L$ $R$ ($1 \le L < R \le N, R - L + 1 \ge 3$), finn:

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

Med andre ord, finn summen av poengsummer over alle deltabeller med lengde minst $3$ som er fullstendig inneholdt i $A_L, A_{L+1}, \dots, A_R$.

Inndata

Inndataene gis i følgende format:

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

Begrensninger

• Alle inndataverdier er heltall.
• $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$ og $R - L + 1 \ge 3$.
• Det er garantert at summen av $N$ over alle testtilfeller ikke overstiger $5 \times 10^5$.
• Det er garantert at summen av $Q$ over alle testtilfeller ikke overstiger $5 \times 10^5$.

Utdata

For hver spørring, skriv ut et enkelt heltall: summen av poengsummer over alle deltabeller med lengde minst $3$ som er fullstendig inneholdt i $A_L, A_{L+1}, \dots, A_R$.

Eksempel

Inndata 1

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

Utdata 1

6
2
2
1

Merk

Testtilfelle 1: For spørringen $[1, 5]$ er deltabellene med lengde minst $3$:

• $[2, 5, 1]$, poengsum $= 1$
• $[5, 1, 3]$, poengsum $= 0$
• $[1, 3, 4]$, poengsum $= 1$
• $[2, 5, 1, 3]$, poengsum $= 1$
• $[5, 1, 3, 4]$, poengsum $= 1$
• $[2, 5, 1, 3, 4]$, poengsum $= 2$

Dermed er svaret $6$.