Нехай $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$.