Soit $B$ un tableau de longueur $M$. Le score de $B$ est le nombre d'indices $i$ ($2 \le i \le M - 1$) tels qu'il existe des indices $x$ et $y$ avec $1 \le x < i < y \le M$ et $2 \cdot B_i > B_x + B_y$.

On vous donne un tableau $A$ de longueur $N$.

Vous devez répondre à $Q$ requêtes.

Pour chaque requête $L$ $R$ ($1 \le L < R \le N, R - L + 1 \ge 3$), trouvez :

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

En d'autres termes, trouvez la somme des scores sur tous les sous-tableaux de longueur au moins $3$ qui sont entièrement contenus dans $A_L, A_{L+1}, \dots, A_R$.

Entrée

L'entrée est donnée dans le format suivant :

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

Contraintes

• Toutes les valeurs d'entrée sont des entiers.
• $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$ et $R - L + 1 \ge 3$.
• Il est garanti que la somme de $N$ sur l'ensemble des cas de test ne dépasse pas $5 \times 10^5$.
• Il est garanti que la somme de $Q$ sur l'ensemble des cas de test ne dépasse pas $5 \times 10^5$.

Sortie

Pour chaque requête, affichez un seul entier : la somme des scores sur tous les sous-tableaux de longueur au moins $3$ entièrement contenus dans $A_L, A_{L+1}, \dots, A_R$.

Exemple

Entrée 1

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

Sortie 1

6
2
2
1

Note

Cas de test 1 : Pour la requête $[1, 5]$, les sous-tableaux de longueur au moins $3$ sont :

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

Ainsi, la réponse est $6$.