Misalkan $B$ adalah sebuah array dengan panjang $M$. Skor (score) dari $B$ adalah banyaknya indeks $i$ ($2 \le i \le M - 1$) sedemikian sehingga terdapat indeks $x$ dan $y$ dengan $1 \le x < i < y \le M$ dan $2 \cdot B_i > B_x + B_y$.

Anda diberikan sebuah array $A$ dengan panjang $N$.

Anda perlu menjawab $Q$ kueri.

Untuk setiap kueri $L$ $R$ ($1 \le L < R \le N, R - L + 1 \ge 3$), carilah:

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

Dengan kata lain, carilah jumlah skor dari semua subarray dengan panjang setidaknya $3$ yang sepenuhnya termuat di dalam $A_L, A_{L+1}, \dots, A_R$.

Masukan

Masukan diberikan dalam format berikut:

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

Batasan

• Semua nilai masukan adalah bilangan bulat.
• $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$ dan $R - L + 1 \ge 3$.
• Dijamin bahwa jumlah dari $N$ di semua kasus uji tidak melebihi $5 \times 10^5$.
• Dijamin bahwa jumlah dari $Q$ di semua kasus uji tidak melebihi $5 \times 10^5$.

Keluaran

Untuk setiap kueri, cetak sebuah bilangan bulat: jumlah skor dari semua subarray dengan panjang setidaknya $3$ yang sepenuhnya termuat di dalam $A_L, A_{L+1}, \dots, A_R$.

Contoh

Masukan 1

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

Keluaran 1

6
2
2
1

Catatan

Kasus uji 1: Untuk kueri $[1, 5]$, subarray dengan panjang setidaknya $3$ adalah:

• $[2, 5, 1]$, skor $= 1$
• $[5, 1, 3]$, skor $= 0$
• $[1, 3, 4]$, skor $= 1$
• $[2, 5, 1, 3]$, skor $= 1$
• $[5, 1, 3, 4]$, skor $= 1$
• $[2, 5, 1, 3, 4]$, skor $= 2$

Dengan demikian, jawabannya adalah $6$.