$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$입니다.