#P18024. Score Queries

Score Queries

Score Queries

对于一个长度为 MM 的数组 BB,定义它的分数 score⁡(B)\operatorname{score}(B) 为满足下述条件的下标 ii 的数量:

  • 2≤i≤M−12\le i\le M-1;
  • 存在 1≤x<i<y≤M1\le x<i<y\le M,使得 2Bi>Bx+By2B_i>B_x+B_y。

给定长度为 NN 的数组 AA,回答 QQ 个询问。每个询问给出 L,RL,R,保证 R−L+1≥3R-L+1\ge3。求区间 [L,R][L,R] 内所有长度至少为 33 的连续子数组的分数之和,即

$$\sum_{i=L}^{R-2}\sum_{j=i+2}^{R}\operatorname{score}(A_i,A_{i+1},\ldots,A_j).$$

输入格式

第一行一个整数 TT,表示测试用例数。每组数据的格式如下:

  • 第一行两个整数 N,QN,Q。
  • 第二行 NN 个整数 A1,…,ANA_1,\ldots,A_N。
  • 接下来 QQ 行,每行两个整数 L,RL,R,表示一次询问。

输出格式

按输入顺序,每个询问输出一行一个整数,表示分数之和。答案不取模。

数据范围

1≤T≤1041\le T\le10^4,3≤N≤5×1053\le N\le5\times10^5,1≤Q≤5×1051\le Q\le5\times10^5,1≤Ai≤N1\le A_i\le N,1≤L<R≤N1\le L<R\le N,R−L+1≥3R-L+1\ge3。

所有测试用例的 NN 之和不超过 5×1055\times10^5,QQ 之和也不超过 5×1055\times10^5。

样例 1

输入

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

输出

6
2
2
1