Пусть $B$ — массив длины $M$. Счётом (score) массива $B$ называется количество индексов $i$ ($2 \le i \le M - 1$), таких что существуют индексы $x$ и $y$, для которых $1 \le x < i < y \le M$ и $2 \cdot B_i > B_x + B_y$.

Вам дан массив $A$ длины $N$.

Вам нужно ответить на $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)$$

Другими словами, найдите сумму счётов по всем подмассивам длины не менее $3$, которые полностью содержатся внутри $A_L, A_{L+1}, \dots, A_R$.

Входные данные

Входные данные даны в следующем формате:

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$.

Выходные данные

Для каждого запроса выведите одно целое число: сумму счётов по всем подмассивам длины не менее $3$, полностью содержащимся в $A_L, A_{L+1}, \dots, A_R$.

Пример

Входные данные 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$.