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

#define rep(i,a,b) for(int i = (a); i < (b); ++i)
#define all(x) begin(x),end(x)
#define sz(x) int(x.size())
typedef vector<int> vi;
typedef vector<vi> vvi;
typedef long long ll;

void solve(){
    int n,q; cin >> n >> q;

    vi a(n);
    for(auto& c : a) cin >> c;

    vector<array<int,3>> qs(q);
    rep(i,0,q){
        int l,r; cin >> l >> r;
        --l;
        qs[i] = {l,r,i};
    }

    vi ans(q,-1);

    auto brute = [&](int l, int r) -> int {
        vi dp;
        rep(i,l,r){
            int x = a[i];
            auto it = lower_bound(all(dp),x);
            if (it == end(dp)){
                dp.push_back(x);
            }else{
                *it = x;
            }
        }
        return sz(dp);
    };

    auto rec = [&](int l, int r, vector<array<int,3>> q, auto&& rec) -> void {
        if (sz(q) == 0) return;

        decltype(q) toleft, toright;

        int m = (l+r)/2;

        vi lnum(m-l+1), rnum(r-m+1);

        {
            vi dp;
            rep(len,1,sz(rnum)){
                int x = a[m + len - 1];
                auto it = lower_bound(all(dp), x);
                if (it == end(dp)){
                    dp.push_back(x);
                }else{
                    *it = x;
                }
                rnum[len] = sz(dp);
            }
        }

        {
            vi dp;
            rep(len,1,sz(lnum)){
                int x = -a[m - len];
                auto it = lower_bound(all(dp), x);
                if (it == end(dp)){
                    dp.push_back(x);
                }else{
                    *it = x;
                }
                lnum[len] = sz(dp);
            }
        }

        for(auto cur : q){
            if (cur[1] - cur[0] < 20){ 

            }else if (cur[0] <= m and cur[1] >= m){
                int mx = max(rnum[cur[1] - m], lnum[m - cur[0]]);
                ans[cur[2]] = mx*3/2;
            }else if (cur[1] < m){
                // left
                toleft.push_back(cur);
            }else{
                // right
                toright.push_back(cur);
            }
        }

        rec(l,m,toleft,rec);
        rec(m,r,toright,rec);
    };  

    rec(0,n,qs,rec);

    rep(i,0,q) if (ans[i] < 0){
        ans[i] = brute(qs[i][0],qs[i][1]);
    }

    // rep(i,0,q) {
    //     int val = brute(qs[i][0],qs[i][1]);
    //     assert(ans[i] <= val*3/2);
    //     assert(val <= ans[i]*3/2);
    // }

    for(auto c : ans) cout << c << '\n';
}

int main(){
    cin.tie(0)->sync_with_stdio(0);
    

    int t; cin >> t;
    while(t--) solve();
}