Score Queries
对于一个长度为 M 的数组 B,定义它的分数 score(B) 为满足下述条件的下标 i 的数量:
- 2≤i≤M−1;
- 存在 1≤x<i<y≤M,使得 2Bi>Bx+By。
给定长度为 N 的数组 A,回答 Q 个询问。每个询问给出 L,R,保证 R−L+1≥3。求区间 [L,R] 内所有长度至少为 3 的连续子数组的分数之和,即
$$\sum_{i=L}^{R-2}\sum_{j=i+2}^{R}\operatorname{score}(A_i,A_{i+1},\ldots,A_j).$$
输入格式
第一行一个整数 T,表示测试用例数。每组数据的格式如下:
- 第一行两个整数 N,Q。
- 第二行 N 个整数 A1,…,AN。
- 接下来 Q 行,每行两个整数 L,R,表示一次询问。
输出格式
按输入顺序,每个询问输出一行一个整数,表示分数之和。答案不取模。
数据范围
1≤T≤104,3≤N≤5×105,1≤Q≤5×105,1≤Ai≤N,1≤L<R≤N,R−L+1≥3。
所有测试用例的 N 之和不超过 5×105,Q 之和也不超过 5×105。
样例 1
输入
1
5 4
2 5 1 3 4
1 5
2 5
1 4
3 5
输出
6
2
2
1