Gọi $B$ là một mảng có độ dài $M$. Điểm số (score) của $B$ là số lượng chỉ số $i$ ($2 \le i \le M - 1$) sao cho tồn tại các chỉ số $x$ và $y$ thỏa mãn $1 \le x < i < y \le M$ và $2 \cdot B_i > B_x + B_y$.

Bạn được cho một mảng $A$ có độ dài $N$.

Bạn cần trả lời $Q$ truy vấn.

Với mỗi truy vấn $L$ $R$ ($1 \le L < R \le N, R - L + 1 \ge 3$), hãy tìm:

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

Nói cách khác, hãy tìm tổng điểm số của tất cả các mảng con có độ dài ít nhất là $3$ nằm hoàn toàn bên trong $A_L, A_{L+1}, \dots, A_R$.

Dữ liệu vào

Dữ liệu vào được cho theo định dạng sau:

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

Giới hạn

• Tất cả các giá trị đầu vào đều là số nguyên.
• $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$ và $R - L + 1 \ge 3$.
• Đảm bảo rằng tổng của $N$ trên tất cả các bộ test không vượt quá $5 \times 10^5$.
• Đảm bảo rằng tổng của $Q$ trên tất cả các bộ test không vượt quá $5 \times 10^5$.

Dữ liệu ra

Với mỗi truy vấn, in ra một số nguyên duy nhất: tổng điểm số của tất cả các mảng con có độ dài ít nhất là $3$ nằm hoàn toàn bên trong $A_L, A_{L+1}, \dots, A_R$.

Ví dụ

Dữ liệu vào 1

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

Dữ liệu ra 1

6
2
2
1

Giải thích

Test case 1: Với truy vấn $[1, 5]$, các mảng con có độ dài ít nhất là $3$ bao gồm:

• $[2, 5, 1]$, điểm số $= 1$
• $[5, 1, 3]$, điểm số $= 0$
• $[1, 3, 4]$, điểm số $= 1$
• $[2, 5, 1, 3]$, điểm số $= 1$
• $[5, 1, 3, 4]$, điểm số $= 1$
• $[2, 5, 1, 3, 4]$, điểm số $= 2$

Do đó, câu trả lời là $6$.