#include <bits/stdc++.h>

using namespace std;

namespace std {
#ifndef LOCAL
#define cerr \
  if (0) cerr
#endif
}  // namespace std

int a[200005];
int dp[200005][2];
int n, q;

int32_t main() {
  ios_base::sync_with_stdio(0);
  cin.tie(0);
#ifdef LOCAL
#define task "a"
#else
#define task "CLIMBING"
#endif
  if (fopen(task ".inp", "r")) {
    freopen(task ".inp", "r", stdin);
    freopen(task ".out", "w", stdout);
  }
  cin >> n >> q;
  for (int i = 1; i <= n; i++) {
    cin >> a[i];
  }
  while (q--) {
    int l, r;
    cin >> l >> r;
    // dp[i, last_sign]
    // sign = 0: <
    // sign = 1: >
    int ret = 0;
    for (int i = l; i <= r; i++) {
      dp[i][1] = 1;
      dp[i][0] = -1e9;
      for (int j = l; j < i; j++) {
        if (a[j] < a[i]) {
          dp[i][0] = max(dp[i][0], dp[j][1] + 1);
        }
        if (a[j] > a[i]) {
          dp[i][1] = max(dp[i][1], dp[j][0] + 1);
        }
      }
      ret = max(ret, dp[i][1]);
    }
    cout << ret << "\n";
  }
  return 0;
}