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

template <typename T> void set_min(T& a, const T& b){
	if(b < a) a = b;
}
template <typename T> void set_max(T& a, const T& b){
	if(b > a) a = b;
}

namespace std {

	template<class Fun>
	class y_combinator_result {
		Fun fun_;
	public:
		template<class T>
		explicit y_combinator_result(T &&fun): fun_(std::forward<T>(fun)) {}
	
		template<class ...Args>
		decltype(auto) operator()(Args &&...args) {
			return fun_(std::ref(*this), std::forward<Args>(args)...);
		}
	};
	
	template<class Fun>
	decltype(auto) y_combinator(Fun &&fun) {
		return y_combinator_result<std::decay_t<Fun>>(std::forward<Fun>(fun));
	}
	
} // namespace std
	
void solve(){
	int N, Q;
	cin >> N >> Q;
	vector<int> A(N);
	for(int i = 0; i < N; i++) cin >> A[i];
	vector<pair<int,int> > queries(Q);
	for(int q = 0; q < Q; q++){
		int L, R;
		cin >> L >> R;
		L--; R--;
		queries[q] = {L, R};
	}
	vector<int> answers(Q);

	vector<int> all_idxs(Q);
	for(int q = 0; q < Q; q++) all_idxs[q] = q;

	vector<vector<int> > ltmp(N), rtmp(N);
	y_combinator(
		[&](auto self, int l, int r, vector<int> qidxs) -> void {
			if(l > r) return;
			vector<int> lidxs, ridxs;
			int m = (l+r)/2;
			for(int i = l; i <= r; i++){
				ltmp[i] = {}; rtmp[i] = {};
			}
			for(int qidx : qidxs){
				auto [ql, qr] = queries[qidx];
				if(qr < m){
					lidxs.push_back(qidx);
				} else if(ql > m){
					ridxs.push_back(qidx);
				} else {
					ltmp[ql].push_back(qidx);
					rtmp[qr].push_back(qidx);
				}
			}
			{
				vector<int> best = {};
				for(int i = m; i <= r; i++){
					int idx = (int)(lower_bound(best.begin(), best.end(), A[i]) - best.begin());
					if(idx == (int)best.size()) best.push_back(-1);
					best[idx] = A[i];
					for(int qidx : rtmp[i]){
						set_max(answers[qidx], (int)best.size());
					}
				}
			}
			{
				vector<int> best = {};
				for(int i = m; i >= l; i--){
					int idx = (int)(lower_bound(best.begin(), best.end(), -A[i]) - best.begin());
					if(idx == (int)best.size()) best.push_back(-1);
					best[idx] = -A[i];
					for(int qidx : ltmp[i]){
						set_max(answers[qidx], (int)best.size());
					}
				}
			}
			self(l, m-1, lidxs);
			self(m+1, r, ridxs);
		}
	)(0, N-1, all_idxs);
	for(int a : answers){
		cout << (3*a/2) << '\n';
	}
}

int main(){
	ios_base::sync_with_stdio(false), cin.tie(nullptr);
	int T;
	cin >> T;
	while(T--) solve();
}
