#ifndef __APPLE__
#include <bits/stdc++.h>
#else
#include <iostream>
#include <vector>
#include <set>
#include "map"
#include "iomanip"
#include "cassert"
#include "numbers"
#include "random"
#endif
using namespace std;
#define all(x) x.begin(), x.end()
#define int long long
typedef long double ld;
struct segtree {
    vector<int> tree;
    int sz;
    int mx = 0;
    void init(int n) {
        sz = 1;
        mx = 0;
        while (sz < n) {
            sz *= 2;
        }
        tree.assign(sz * 2, 2e9);
    }
    void ch(int v, int vl) {
        v += sz;
        tree[v] = min(tree[v], vl);
        while (v != 1) {
            v /= 2;
            tree[v] = max(tree[v * 2], tree[v * 2 + 1]);
        }

    }
    int getx(int trg) {
        int v = 1;
        while (v < sz) {
            if (tree[v * 2] >= trg) {
                v *= 2;
            } else {
                v = v * 2 + 1;
            }
        }
        return v-sz;
    }
    void addt(int vl) {
        int ps = getx(vl);
        ch(ps, vl);
        mx = max(mx, ps+1);
    }
};
vector<int> a;
vector<int> ans;
vector<vector<int>> steps;
void solve(int l, int r, vector<array<int, 3>> qur) {
    if (qur.empty())
        return;
    int m = l + r >> 1;
    vector<array<int, 3>> ql, qr;
    for (auto [l1, r1, ind] : qur) {
        if (l1 <= m and m <= r1) {
            steps[l1].push_back(ind);
            steps[r1].push_back(ind);
        } else if (l1 < m) {
            ql.push_back({l1, r1, ind});
        } else {
            qr.push_back({l1, r1, ind});
        }
    }
    segtree sg;
    sg.init(r-m+1);
    for (int i = m; i <= r; ++i) {
        if (!steps[i].empty()) {
            for (auto iq : steps[i])
                ans[iq] += sg.mx;
            steps[i].clear();
        }
        if (i != r)
            sg.addt(a[i]);
    }
    sg.init(m-l+1);
    for (int i = m-1; i >= l; --i) {
        sg.addt(((int)1e9)-a[i]);
        if (!steps[i].empty()) {
            for (auto iq : steps[i]) {
                if (ans[iq] == 1 and sg.mx == 1) {
                    if (a[m-1] < a[m])
                        ans[iq]--;
                }
                ans[iq] += sg.mx;
            }
            steps[i].clear();
        }
    }
    solve(l, m, ql);
    solve(m, r, qr);
}
void solve() {
    int n, m;
    cin >> n >> m;
    a.assign(n, {});
    steps.assign(n+1, {});
    ans.assign(m, {});
    vector<array<int, 3>> q(m);
    for (int i = 0; i < n; ++i) {
        cin >> a[i];
    }
    for (int i = 0; i < m; ++i) {
        cin >> q[i][0] >> q[i][1];
        q[i][2] = i;
        q[i][0]--;
    }
    solve(0, n, q);
    for (int i = 0; i < m; ++i) {
        //cout << ans[i] << '\n';
        cout << (ans[i] * 2 + 2) / 3 << '\n';
    }
}
signed main() {
    cin.tie(0);
    cout.tie(0);
    ios_base::sync_with_stdio(0);
    /*
    for (int i = 1; i < 200000; ++i) {
        int k = i * 2;
        k = (k * 2 + 2) / 3;
        if (k*2 > 3*i)
            cout << i << '\n';
    }exit(0);*/
    int t = 1;
    cin >> t;
    while (t--)
        solve();
}
/*

 */