Látum $B$ vera fylki af lengd $M$. Stig (score) fylkisins $B$ er fjöldi vísa $i$ ($2 \le i \le M - 1$) þannig að til séu vísar $x$ og $y$ með $1 \le x < i < y \le M$ og $2 \cdot B_i > B_x + B_y$.

Þér er gefið fylki $A$ af lengd $N$.

Þú þarft að svara $Q$ fyrirspurnum.

Fyrir hverja fyrirspurn $L$ $R$ ($1 \le L < R \le N, R - L + 1 \ge 3$), finndu:

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

Með öðrum orðum, finndu summu stiga yfir öll hlutfylki af lengd að minnsta kosti $3$ sem eru مکملlega innan $A_L, A_{L+1}, \dots, A_R$.

Inntak

Inntakið er gefið á eftirfarandi sniði:

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

Skorður

• Öll inntaksgildi eru heiltölur.
• $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$.
• Það er tryggt að summa $N$ yfir öll prófunartilvik fari ekki yfir $5 \times 10^5$.
• Það er tryggt að summa $Q$ yfir öll prófunartilvik fari ekki yfir $5 \times 10^5$.

Úttak

Fyrir hverja fyrirspurn skaltu prenta eina heiltölu: summu stiga yfir öll hlutfylki af lengd að minnsta kosti $3$ sem eru مکملlega innan $A_L, A_{L+1}, \dots, A_R$.

Dæmi

Inntak 1

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

Úttak 1

6
2
2
1

Athugasemd

Prófunartilvik 1: Fyrir fyrirspurnina $[1, 5]$ eru hlutfylkin af lengd að minnsta kosti $3$:

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

Því er svarið $6$.