设 $B$ 是一个长度为 $M$ 的数组。$B$ 的分数（score）是满足以下条件的下标 $i$ ($2 \le i \le M - 1$) 的数量：存在下标 $x$ 和 $y$ 满足 $1 \le x < i < y \le M$ 且 $2 \cdot B_i > B_x + B_y$。

给你一个长度为 $N$ 的数组 $A$。

你需要回答 $Q$ 个询问。

对于每个询问 $L$ $R$ ($1 \le L < R \le N, R - L + 1 \ge 3$)，求：

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

换句话说，求完全包含在 $A_L, A_{L+1}, \dots, A_R$ 内的所有长度至少为 3 的子数组的分数之和。

输入格式

输入格式如下：

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

数据范围

• 所有输入值均为整数。
• $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$ 且 $R - L + 1 \ge 3$。
• 保证所有测试用例中 $N$ 的总和不超过 $5 \times 10^5$。
• 保证所有测试用例中 $Q$ 的总和不超过 $5 \times 10^5$。

输出格式

对于每个询问，输出一个整数：完全包含在 $A_L, A_{L+1}, \dots, A_R$ 内的所有长度至少为 3 的子数组的分数之和。

样例

输入格式 1

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

输出格式 1

6
2
2
1

说明

测试用例 1：对于询问 $[1, 5]$，长度至少为 3 的子数组有：

• $[2, 5, 1]$，分数 $= 1$
• $[5, 1, 3]$，分数 $= 0$
• $[1, 3, 4]$，分数 $= 1$
• $[2, 5, 1, 3]$，分数 $= 1$
• $[5, 1, 3, 4]$，分数 $= 1$
• $[2, 5, 1, 3, 4]$，分数 $= 2$

因此，答案为 6。