$B$ ұзындығы $M$ болатын массив болсын. $B$ массивінің ұпайы (score) деп $1 \le x < i < y \le M$ және $2 \cdot B_i > B_x + B_y$ болатындай $x$ пен $y$ индекстері табылатын $i$ ($2 \le i \le M - 1$) индекстерінің санын айтамыз.

Сізге ұзындығы $N$ болатын $A$ массиві берілген.

Сізге $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)$$

Басқаша айтқанда, $A_L, A_{L+1}, \dots, A_R$ ішінде толығымен жататын ұзындығы кемінде $3$ болатын барлық ішкі массивтердің ұпайларының қосындысын табыңыз.

Кіріс деректер

Кіріс деректер келесі форматта беріледі:

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$-нен аспайтынына кепілдік беріледі.

Шығыс деректер

Әрбір сұраным үшін бір бүтін санды шығарыңыз: $A_L, A_{L+1}, \dots, A_R$ ішінде толығымен жататын ұзындығы кемінде $3$ болатын барлық ішкі массивтердің ұпайларының қосындысы.

Мысал

Кіріс деректер 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$ болады.