#include<bits/stdc++.h>

#ifdef LOCAL
#define debug(...) [](auto...a){((cout << a << ' '), ...) << endl; }(#__VA_ARGS__, ": ", __VA_ARGS__)
#define debugv(v) do { cout << #v << ": "; for (auto x : v) cout << x << ' ';cout << endl; } while(0)
#else
#define debug(...)
#define debugv(v) 
#endif

using namespace std;

void solve();

int32_t main() {
	cin.tie(0); ios_base::sync_with_stdio(0);
	int t = 1;
	cin >> t;
	while(t--) solve();
}

template<typename T, typename U>
struct SegmentTree {
    int h, n;
    T neutral;
    U unite;
    vector<T> data;

    template<typename I>
    SegmentTree(int sz, T neutral, U unite, I init) : h(__lg(sz) + 1), n(1 << h), neutral(neutral), unite(unite), data(2 * n) {
        for (int i = 0; i < sz; ++i) data[i + n] = init(i);
        for (int i = n - 1; i > 0; --i) data[i] = unite(data[2 * i], data[2 * i + 1]);
    }

    SegmentTree(int sz, T neutral, U unite) : h(__lg(sz) + 1), n(1 << h), neutral(neutral), unite(unite), data(2 * n, neutral) {}

    void set(int i, T x) {
        data[i += n] = x;
        for (i /= 2; i > 0; i /= 2) data[i] = unite(data[2 * i], data[2 * i + 1]);
    }

    T get(int l, int r) {
        T leftRes = neutral, rightRes = neutral;
        for (l += n, r += n; l < r; l /= 2, r /= 2) {
            if (l & 1) leftRes = unite(leftRes, data[l++]);
            if (r & 1) rightRes = unite(data[--r], rightRes);
        }
        return unite(leftRes, rightRes);
    }
};

void solve() {
	int n, q;
	cin >> n >> q;
	vector<int> a(n);
	for (int &x : a) cin >> x;
	for (int &x : a) --x;
	
	int b = __lg(n) + 1;
	
	vector<int> level(n + 1, b);
	vector<vector<int>> lf(b, vector<int>(n)), rg(b, vector<int>(n + 1));
	SegmentTree lis(n, 0, [](int x, int y) { return max(x, y); });
	
	auto go = [&](auto go, int l, int r, int lvl) {
		if (l >= r) return;
		
		int m = (l + r) / 2;
		level[m] = lvl;
		
		for (int i = m; i < r; ++i) {
			int p = lis.get(0, a[i]);
			lis.set(a[i], p + 1);
			rg[lvl][i + 1] = lis.get(0, n);
		}
		for (int i = m; i < r; ++i) lis.set(a[i], 0);
		
		for (int i = m - 1; i >= l; --i) {
			int p = lis.get(a[i] + 1, n);
			lis.set(a[i], p + 1);
			lf[lvl][i] = lis.get(0, n);
		}
		for (int i = l; i < m; ++i) lis.set(a[i], 0);
		
		go(go, l, m - 1, lvl + 1);
		go(go, m + 1, r, lvl + 1);
	};
	go(go, 0, n, 0);
	
	SegmentTree levels(n + 1, pair{b, -1}, [](auto x, auto y) { return min(x, y); }, [&](int i) { return pair{level[i], i}; });
	
	for (int j = 0; j < q; ++j) {
		int l, r;
		cin >> l >> r;
		--l;
		auto [lvl, m] = levels.get(l, r + 1);
		int left = lf[lvl][l];
		int right = rg[lvl][r];
		int low = max(left, right);
		int high = left + right;
		int ans = (low + high) / 2;
	    cout << ans << '\n';
	}
}
