#include<bits/stdc++.h>
using namespace std;
#define int long long
struct Zap
{
	int l,p;
};
struct Node
{
	int a,b,dod;
};
int tab[2000009];
long long Tre[4000000];
long long odp[500009];
int base;
void Przedzial(int l, int  p, int dod)
{
	l+=base;
	p+=base;
	while(l<=p)
	{
		if(l%2==1)
		{
			Tre[l]+=dod;
			l++;
		}
		if(p%2==0)
		{
			Tre[p]+=dod;
			p--;
		}
		l>>=1;
		p>>=1;
	}
}
long long Punkt(int v)
{
	v+=base;
	long long wynik=0;
	while(v>0)
	{
		wynik+=Tre[v];
		v>>=1;
	}
	return wynik;
}
int TworzenieDzrewa(int x)
{
	int u=1;
	while(x>0)
	{
		x>>=1;
		u<<=1;
	}
	return u;
}
vector<Node>VV[1000009];
vector<pair<int,int>>V[1000009];
int32_t main()
{ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0);
int N;
cin>>N;
for(int I=1;I<=N;I++)
{
	int n,q;
	cin>>n>>q;
	base=TworzenieDzrewa(1000000);
	for(int i=1;i<=base*2;i++)
	{
		Tre[i]=0;
	}
	for(int i=1;i<=1000000;i++)
	{
		VV[i].clear();
		V[i].clear();
	}
	vector<Zap>Z;
	for(int i=1;i<=n;i++)
	{
		cin>>tab[i];
	}
	for(int i=1;i<=q;i++)
	{
		int a,b;
		cin>>a>>b;
		V[a].push_back({b,i});
	}
	vector<pair<int,int>>maxx,minn;
	maxx.push_back({INT_MAX,0});
	minn.push_back({0,0});
	for(int i=1;i<=n;i++)
	{
		while(maxx.back().first<=tab[i])
		{
			maxx.pop_back();
		}
		while(minn.back().first>=tab[i])
		{
			minn.pop_back();
		}
		maxx.push_back({tab[i],i});
		minn.push_back({tab[i],i});
		vector<pair<int,Zap>>U;
		U.push_back({0,{0,0}});
		int h1=1,h2=1;
		while(true)
		{
			if(h1<maxx.size()&&h2<minn.size())
			{
				if(maxx[h1].second<minn[h2].second)
				{
					U.push_back({maxx[h1].second,{0,0}});
					h1++;
				}
				else
				{
					U.push_back({minn[h2].second,{0,0}});
					h2++;
				}
			}
			else if(h1<maxx.size())
			{
				U.push_back({maxx[h1].second,{0,0}});
				h1++;
			}
			else if(h2<minn.size())
			{
				U.push_back({minn[h2].second,{0,0}});
				h2++;
			}
			else{break;}
			if(U.size()>=2&&U[U.size()-2].first==U[U.size()-1].first){U.pop_back();}
		}
		int l=INT_MAX,p=0;
		for(int j=U.size()-1;j>=1;j--)
		{
			p=max(p,tab[U[j].first]);
			l=min(l,tab[U[j].first]);
			U[j].second={l,p};
		}
		for(int j=1;j<U.size();j++)
		{
			int dl=U[j].first-U[j-1].first;
			VV[1].push_back({U[j].second.p,1000000,dl});
			VV[U[j].second.l+1].push_back({U[j].second.p,1000000,-dl});
		}
	}
	for(int i=1;i<=1000000;i++)
	{
		for(int j=0;j<VV[i].size();j++)
		{
			Przedzial(VV[i][j].a,VV[i][j].b,VV[i][j].dod);
		}
		for(int j=0;j<V[i].size();j++)
		{
			odp[V[i][j].second]=Punkt(V[i][j].first);
		}
	}
	for(int i=1;i<=q;i++)
	{
		cout<<odp[i]<<'\n';
	}
}
	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
**/