Olkoon $B$ taulukko, jonka pituus on $M$. Taulukon $B$ pistemäärä (score) on sellaisten indeksien $i$ ($2 \le i \le M - 1$) lukumäärä, joille on olemassa indeksit $x$ ja $y$ siten, että $1 \le x < i < y \le M$ ja $2 \cdot B_i > B_x + B_y$.

Sinulle annetaan taulukko $A$, jonka pituus on $N$.

Sinun tulee vastata $Q$ kyselyyn.

Jokaista kyselyä $L$ $R$ ($1 \le L < R \le N, R - L + 1 \ge 3$) kohden laske:

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

Toisin sanoen, etsi kaikkien sellaisten vähintään pituuden $3$ osataulukoiden pistemäärien summa, jotka sisältyvät kokonaan väliin $A_L, A_{L+1}, \dots, A_R$.

Syöte

Syöte annetaan seuraavassa muodossa:

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

Rajoitukset

• Kaikki syötearvot ovat kokonaislukuja.
• $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$ ja $R - L + 1 \ge 3$.
• On taattu, että arvojen $N$ summa yli kaikkien testitapausten ei ylitä arvoa $5 \times 10^5$.
• On taattu, että arvojen $Q$ summa yli kaikkien testitapausten ei ylitä arvoa $5 \times 10^5$.

Tuloste

Tulosta jokaista kyselyä kohden yksi kokonaisluku: kaikkien väliin $A_L, A_{L+1}, \dots, A_R$ kokonaan sisältyvien vähintään pituuden $3$ osataulukoiden pistemäärien summa.

Esimerkki

Syöte 1

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

Tuloste 1

6
2
2
1

Huomautus

Testitapaus 1: Kyselylle $[1, 5]$ vähintään pituuden $3$ osataulukot ovat:

• $[2, 5, 1]$, pistemäärä $= 1$
• $[5, 1, 3]$, pistemäärä $= 0$
• $[1, 3, 4]$, pistemäärä $= 1$
• $[2, 5, 1, 3]$, pistemäärä $= 1$
• $[5, 1, 3, 4]$, pistemäärä $= 1$
• $[2, 5, 1, 3, 4]$, pistemäärä $= 2$

Siispä vastaus on $6$.