#include <bits/extc++.h>
#define endl '\n'
typedef long long ll;
#define int ll
using namespace std;
using namespace __gnu_cxx;
using namespace __gnu_pbds;

int lg[2001];

void Main() {
  int n, q;
  cin >> n >> q;
  vector a(n + 1, 0ll);
  vector st(n + 1, vector(lg[n] + 1, 0ll)), pre(n + 2, vector(n + 2, 0ll));
  for (int i = 1; i <= n; ++i) {
    cin >> a[i];
    st[i][0] = a[i];
  }
  for (int j = 1; j <= lg[n]; ++j) {
    for (int i = 1; i + (1ll << j) - 1 <= n; ++i) {
      st[i][j] = min(st[i][j - 1], st[i + (1ll << (j - 1))][j - 1]);
    }
  }
  for (int l = 1; l <= n; ++l) {
    int mx = 0;
    for (int i = l; i < n; ++i) {
      mx = max(mx, a[i]);
      int r = i + 1;
      if (a[r] < mx) continue;
      for (int j = lg[n]; j >= 0; --j)
        if (r + (1ll << j) - 1 <= n && st[r][j] > mx)
          r += 1ll << j;
      ++pre[l][i + 1];
      ++pre[l][r];
    }
    for (int i = l; i <= n; ++i)
      pre[l][i] += pre[l][i - 1];
  }
  while (q--) {
    int l, r;
    cin >> l >> r;
    cout << pre[l][r] << endl;
  }
}

#define __CP_MULTI_TEST_CASES

signed main() {
  ios::sync_with_stdio(false), cin.tie(0), cout.tie(0);
  lg[1] = 0;
  for (int i = 2; i <= 2000; ++i) {
    lg[i] = lg[i >> 1] + 1;
  }
  int t = 1;
#ifdef __CP_MULTI_TEST_CASES
  cin >> t;
#endif
  while (t--) {
    Main();
  }
  return 0;
}