#include <bits/stdc++.h>

using namespace std;

#define FOR(i, a, b) for(int i = (a); i < (b); i++)
#define RFOR(i, a, b) for(int i = (a) - 1; i >= (b); i--)
#define SZ(a) int(a.size())
#define ALL(a) a.begin(), a.end()
#define PB push_back
#define MP make_pair
#define F first
#define S second

typedef long long LL;
typedef vector<int> VI;
typedef pair<int, int> PII;
typedef double db;

const int M = 1'000'047;

struct Fenwick
{
	int n;
	vector<LL> t;
	void init(int _n)
	{
		n = _n;
		t.clear();
		t.assign(n, 0);
	}
	void upd(int i, int x)
	{
		for (; i < n; i |= i + 1)
			t[i] += x;
	}
	LL query(int i)
	{
		LL ans = 0;
		for (; i >= 0; i = (i & (i + 1)) - 1)
			ans += t[i];
		return ans;
	}
};

void solve()
{
	int n, k;
	cin >> n >> k;
	VI a(n);
	for (int& ai : a)
		cin >> ai;
	vector<PII> incr, decr;
	vector<vector<pair<int, int>>> vec(M); 
	FOR(i, 0, n)
	{
		while (!incr.empty() && a[i] < incr.back().F)
			incr.pop_back();
		while (!decr.empty() && a[i] > decr.back().F)
			decr.pop_back();
		incr.PB({a[i], i});
		decr.PB({a[i], i});
		int ptrIncr = 0, ptrDecr = 0;
		int last = -1;
		while (true)
		{
			int index;
			int mn = incr[ptrIncr].F, mx = decr[ptrDecr].F;
			if (incr[ptrIncr].S < decr[ptrDecr].S)
			{
				index = incr[ptrIncr].S;
				ptrIncr++;
			}
			else
			{
				index = decr[ptrDecr].S;
				ptrDecr++;
			}
			if (last < index)
			{
				vec[mx].PB({mn, index - last});
			}
			last = index;
			if (index == i)
				break;
		}
	}
	vector<vector<PII>> queries(M);
	FOR(i, 0, k)
	{
		int l, r;
		cin >> l >> r;
		queries[r].PB({l, i});
	}
	vector<LL> ans(k);
	Fenwick fw;
	fw.init(M);
	LL totSum = 0;
	FOR(r, 0, M)
	{
		for (auto [l, cnt] : vec[r])
		{
			fw.upd(l, cnt);
			totSum += cnt;
		}
		for (auto [l, i] : queries[r])
		{
			ans[i] = totSum - fw.query(l - 1);
		}
	}
	FOR(i, 0, k)
		cout << ans[i] << "\n";
}

int main()
{
	ios::sync_with_stdio(0);
	cin.tie(0);
	int t;
	cin >> t;
	while (t--)
		solve();
	return 0;
}