Sei $B$ ein Array der Länge $M$. Der Punktestand (score) von $B$ ist die Anzahl der Indizes $i$ ($2 \le i \le M - 1$), sodass Indizes $x$ und $y$ mit $1 \le x < i < y \le M$ und $2 \cdot B_i > B_x + B_y$ existieren.

Dir ist ein Array $A$ der Länge $N$ gegeben.

Du musst $Q$ Anfragen beantworten.

Bestimme für jede Anfrage $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)$$

Mit anderen Worten: Finde die Summe der Punktestände über alle Teilarrays der Länge mindestens $3$, die vollständig in $A_L, A_{L+1}, \dots, A_R$ enthalten sind.

Eingabe

Die Eingabe erfolgt im folgenden Format:

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

Einschränkungen

• Alle Eingabewerte sind ganze Zahlen.
• $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$ und $R - L + 1 \ge 3$.
• Es wird garantiert, dass die Summe von $N$ über alle Testfälle $5 \times 10^5$ nicht überschreitet.
• Es wird garantiert, dass die Summe von $Q$ über alle Testfälle $5 \times 10^5$ nicht überschreitet.

Ausgabe

Gib für jede Anfrage eine einzige ganze Zahl aus: die Summe der Punktestände über alle Teilarrays der Länge mindestens $3$, die vollständig in $A_L, A_{L+1}, \dots, A_R$ enthalten sind.

Beispiel

Eingabe 1

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

Ausgabe 1

6
2
2
1

Hinweis

Testfall 1: Für die Anfrage $[1, 5]$ lauten die Teilarrays der Länge mindestens $3$:

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

Somit lautet die Antwort $6$.