$B$ を長さ $M$ の配列とします。$B$ のスコア（score）とは、$1 \le x < i < y \le M$ かつ $2 \cdot B_i > B_x + B_y$ を満たすインデックス $x$ と $y$ が存在するようなインデックス $i$（$2 \le i \le M - 1$）の個数です。

長さ $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

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$ です。