Niech $B$ będzie tablicą o długości $M$. Wynikiem (score) tablicy $B$ nazywamy liczbę indeksów $i$ ($2 \le i \le M - 1$), takich że istnieją indeksy $x$ oraz $y$ spełniające $1 \le x < i < y \le M$ oraz $2 \cdot B_i > B_x + B_y$.

Dana jest tablica $A$ o długości $N$.

Musisz odpowiedzieć na $Q$ zapytań.

Dla każdego zapytania $L$ $R$ ($1 \le L < R \le N, R - L + 1 \ge 3$) wyznacz:

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

Innymi słowy, oblicz sumę wyników po wszystkich podtablicach o długości co najmniej $3$, które całkowicie zawierają się w $A_L, A_{L+1}, \dots, A_R$.

Wejście

Wejście podane jest w następującym formacie:

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

Ograniczenia

• Wszystkie wartości wejściowe są liczbami całkowitymi.
• $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$ oraz $R - L + 1 \ge 3$.
• Gwarantuje się, że suma $N$ po wszystkich przypadkach testowych nie przekracza $5 \times 10^5$.
• Gwarantuje się, że suma $Q$ po wszystkich przypadkach testowych nie przekracza $5 \times 10^5$.

Wyjście

Dla każdego zapytania wypisz jedną liczbę całkowitą: sumę wyników po wszystkich podtablicach o długości co najmniej $3$ całkowicie zawartych w $A_L, A_{L+1}, \dots, A_R$.

Przykład

Wejście 1

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

Wyjście 1

6
2
2
1

Uwaga

Przypadek testowy 1: Dla zapytania $[1, 5]$ podtablicami o długości co najmniej $3$ są:

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

Zatem odpowiedź wynosi $6$.