#include <bits/stdc++.h>
using namespace std;

namespace FastIO {
	#define iL (1 << 20)
	char ibuf[iL],*iS = ibuf + iL,*iT = ibuf + iL;
	#define gc() (iS == iT ? (iT = (iS = ibuf) + fread(ibuf,1,iL,stdin),iS == iT ? EOF : *iS++) : *iS++)
	template<typename T>
	inline void read(T &a)
	{
		char ch;int sign = 0;
		for(ch = gc();!isdigit(ch);ch = gc())
			if(ch == '-') sign = 1;
		a = ch & 15;
		for(ch = gc();isdigit(ch);ch = gc())
			a = (a << 3) + (a << 1) + (ch & 15);
		if(sign) a = -a;
	}
	char Out[iL],*iter = Out;
	#define flush() fwrite(Out,1,iter - Out,stdout),iter = Out
	template<typename T>
	inline void write(T x,char end = '\n')
	{
		int c[40],l = 0;if(x < 0) *iter++ = '-',x = -x;
		do c[++l] = x % 10,x /= 10; while(x);
		while(l) *iter++ = c[l--] + '0';
		*iter++ = end;flush();
	}
	#undef iL 
	#undef gc
	#undef flush
}
using namespace FastIO;

const int N = 2e5 + 5,M = 5e5 + 5,V = 1e6 + 5,VL = 1e6;
typedef long long ll;
int n,Q;
int a[N];
int qx[M],qy[M];
long long ans[M];
int st1[N],st2[N],top1,top2;
struct Qry {
	int lim,v;
	Qry(){}
	Qry(const int _lim,const int _v):lim(_lim),v(_v){}
};
vector<Qry> Chg[V];
vector<int> qs[V];
inline void InsQuery(int l1,int r1,int l2,int r2,int v) {
	if(l1 > r1 || l2 > r2) return;
	// printf("l1,r1,l2,r2:%d,%d,%d,%d,%d\n",l1,r1,l2,r2,v);
	Chg[l1].emplace_back(l2,v);
	if(r2 + 1 <= VL) Chg[l1].emplace_back(r2 + 1,-v);
	if(r1 + 1 <= VL) Chg[r1 + 1].emplace_back(l2,-v);
	if(r1 + 1 <= VL && r2 + 1 <= VL) Chg[r1 + 1].emplace_back(r2 + 1,v);
}
struct BIT {
	long long tr[V];
	#define lowbit(x) (x&(-x))
	void init() { memset(tr,0,sizeof tr);}
	inline void upd(int x,int v) { for(int i = x;i <= VL;i += lowbit(i)) tr[i] += v;}
	inline ll Sum(int x) { long long res = 0;for(int i = x;i;i ^= lowbit(i)) res += tr[i];return res;}
};
void GetQry(int id) {
	vector<int> pois;
	for(int i = 1;i <= top1;i++) pois.push_back(st1[i]);
	for(int i = 1;i <= top2;i++) pois.push_back(st2[i]);
	sort(pois.begin(),pois.end());
	pois.erase(unique(pois.begin(),pois.end()));
	int mi = VL,mx = 0;
	for(int i = (int)pois.size() - 1;i >= 0;i--) { // 在 i 处不合法
		if(pois[i] == id) { mi = mx = a[id];continue;}
		if(a[pois[i]] < mi) InsQuery(a[pois[i]] + 1,mi,mx,VL,id - pois[i]);
		else if(a[pois[i]] > mx) InsQuery(1,mi,mx,a[pois[i]] - 1,id - pois[i]);
		mi = min(mi,a[pois[i]]);mx = max(mx,a[pois[i]]);
	}
	InsQuery(1,mi,mx,VL,id);
}
BIT T;
inline void work() {
	read(n);read(Q);
	for(int i = 1;i <= n;i++) read(a[i]);
	for(int i = 1;i < VL;i++) Chg[i].clear(),qs[i].clear();
	top1 = top2 = 0;
	for(int i = 1;i <= n;i++) {
		while(top1 && a[st1[top1]] >= a[i]) --top1;
		while(top2 && a[st2[top2]] <= a[i]) --top2;
		st1[++top1] = i;st2[++top2] = i;
		GetQry(i);
	}
	// puts("done");
	for(int i = 1;i <= Q;i++)
		read(qx[i]),read(qy[i]),qs[qx[i]].push_back(i),ans[i] = 0;
	T.init();
	for(int i = 1;i <= VL;i++) {
		for(auto it : Chg[i])
			T.upd(it.lim,it.v);
		for(auto id : qs[i])
			ans[id] = T.Sum(qy[id]);
	}
	for(int i = 1;i <= Q;i++)
		write(ans[i]);
}
int main() {
	int T;
	read(T);
	while(T--) work();
	return 0;
}
/*
2
10 3
9 9 3 2 1 9 6 9 1 7
1 13
6 6
2 9
5 1
66575 45720 67904 18764 35162
20000 80000
*/