Sia $B$ un array di lunghezza $M$. Il punteggio (score) di $B$ è il numero di indici $i$ ($2 \le i \le M - 1$) tali che esistono indici $x$ e $y$ con $1 \le x < i < y \le M$ e $2 \cdot B_i > B_x + B_y$.

Ti viene dato un array $A$ di lunghezza $N$.

Devi rispondere a $Q$ query.

Per ogni query $L$ $R$ ($1 \le L < R \le N, R - L + 1 \ge 3$), trova:

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

In altre parole, trova la somma dei punteggi su tutti i sottoarray di lunghezza almeno $3$ che sono completamente contenuti in $A_L, A_{L+1}, \dots, A_R$.

Input

L'input è fornito nel seguente formato:

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

Vincoli

• Tutti i valori di input sono numeri interi.
• $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$ e $R - L + 1 \ge 3$.
• È garantito che la somma di $N$ su tutti i casi di test non supera $5 \times 10^5$.
• È garantito che la somma di $Q$ su tutti i casi di test non supera $5 \times 10^5$.

Output

Per ogni query, stampa un singolo numero intero: la somma dei punteggi su tutti i sottoarray di lunghezza almeno $3$ completamente contenuti in $A_L, A_{L+1}, \dots, A_R$.

Esempio

Input 1

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

Output 1

6
2
2
1

Note

Caso di test 1: Per la query $[1, 5]$, i sottoarray di lunghezza almeno $3$ sono:

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

Pertanto, la risposta è $6$.