Sea $B$ un arreglo de longitud $M$. La puntuación (score) de $B$ es el número de índices $i$ ($2 \le i \le M - 1$) tales que existen índices $x$ e $y$ con $1 \le x < i < y \le M$ y $2 \cdot B_i > B_x + B_y$.

Se te da un arreglo $A$ de longitud $N$.

Debes responder $Q$ consultas.

Para cada consulta $L$ $R$ ($1 \le L < R \le N, R - L + 1 \ge 3$), halla:

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

En otras palabras, halla la suma de las puntuaciones de todos los subarreglos de longitud al menos $3$ que están completamente contenidos dentro de $A_L, A_{L+1}, \dots, A_R$.

Entrada

La entrada se proporciona en el siguiente formato:

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

Restricciones

• Todos los valores de entrada son enteros.
• $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$ y $R - L + 1 \ge 3$.
• Se garantiza que la suma de $N$ en todos los casos de prueba no supera $5 \times 10^5$.
• Se garantiza que la suma de $Q$ en todos los casos de prueba no supera $5 \times 10^5$.

Salida

Para cada consulta, imprime un único entero: la suma de las puntuaciones de todos los subarreglos de longitud al menos $3$ completamente contenidos dentro de $A_L, A_{L+1}, \dots, A_R$.

Ejemplo

Entrada 1

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

Salida 1

6
2
2
1

Nota

Caso de prueba 1: Para la consulta $[1, 5]$, los subarreglos de longitud al menos $3$ son:

• $[2, 5, 1]$, puntuación $= 1$
• $[5, 1, 3]$, puntuación $= 0$
• $[1, 3, 4]$, puntuación $= 1$
• $[2, 5, 1, 3]$, puntuación $= 1$
• $[5, 1, 3, 4]$, puntuación $= 1$
• $[2, 5, 1, 3, 4]$, puntuación $= 2$

Por lo tanto, la respuesta es $6$.