/**
 *    author:  tourist
 *    created: 05.11.2025 18:30:53
**/
#include <bits/stdc++.h>

using namespace std;

#ifdef LOCAL
#include "algo/debug.h"
#else
#define debug(...) 42
#endif

int main() {
  ios::sync_with_stdio(false);
  cin.tie(nullptr);
  int tt;
  cin >> tt;
  while (tt--) {
    int n, q;
    cin >> n >> q;
    vector<int> a(n);
    for (int i = 0; i < n; i++) {
      cin >> a[i];
      --a[i];
    }
    vector<int> ql(q), qr(q), res(q);
    for (int i = 0; i < q; i++) {
      cin >> ql[i] >> qr[i];
      --ql[i];
    }
    vector<int> aux(n);
    auto Dfs = [&](auto&& self, int l, int r, const vector<int>& ids) -> void {
      if (r - l == 1) {
        for (int id : ids) {
          res[id] = 1;
        }
        return;
      }
      int mid = (l + r) >> 1;
      vector<int> u;
      auto Insert = [&](int x) {
        auto it = lower_bound(u.begin(), u.end(), x);
        if (it == u.end()) {
          u.push_back(x);
        } else {
          *it = x;
        }
      };
      for (int i = mid - 1; i >= l; i--) {
        Insert(-a[i]);
        aux[i] = int(u.size());
      }
      u.clear();
      for (int i = mid; i < r; i++) {
        Insert(a[i]);
        aux[i] = int(u.size());
      }
      vector<int> l_ids, r_ids;
      for (int id : ids) {
        if (qr[id] <= mid) {
          l_ids.push_back(id);
          continue;
        }
        if (ql[id] >= mid) {
          r_ids.push_back(id);
          continue;
        }
        int x = aux[ql[id]];
        int y = aux[qr[id] - 1];
        int low = max(x, y);
        int high = x + y;
        if (low == 1) {
          res[id] = (a[mid - 1] > a[mid] ? 1 : 2);
        } else {
          res[id] = (low + high) >> 1;
          assert(res[id] * 2 <= 3 * low);
          assert(high * 2 <= 3 * res[id]);
        }
      }
      self(self, l, mid, l_ids);
      self(self, mid, r, r_ids);
    };
    vector<int> ids(q);
    iota(ids.begin(), ids.end(), 0);
    Dfs(Dfs, 0, n, ids);
    for (int i = 0; i < q; i++) {
      cout << res[i] << '\n';
    }
  }
  return 0;
}
