設 $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$。