Let $B$ be an array of length $M$. The score of $B$ is the number of indices $i$ ($2 \le i \le M - 1$) such that there exist indices $x$ and $y$ with $1 \le x < i < y \le M$ and $2 \cdot B_i > B_x + B_y$.

You are given an array $A$ of length $N$.

You need to answer $Q$ queries.

For each query $L$ $R$ ($1 \le L < R \le N, R - L + 1 \ge 3$), find:

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

In other words, find the sum of scores over all subarrays of length at least $3$ that are completely contained within $A_L, A_{L+1}, \dots, A_R$.

Input

The input is given in the following format:

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

Constraints

• All input values are integers.
• $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$ and $R - L + 1 \ge 3$.
• It is guaranteed that the sum of $N$ over all test cases does not exceed $5 \times 10^5$.
• It is guaranteed that the sum of $Q$ over all test cases does not exceed $5 \times 10^5$.

Output

For each query, output a single integer: the sum of scores over all subarrays of length at least $3$ completely contained within $A_L, A_{L+1}, \dots, A_R$.

Example

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

Test case 1: For the query $[1, 5]$, the subarrays of length at least $3$ are:

• $[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$

Thus, the answer is $6$.