#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
int main() {
// Optimize standard I/O operations for competitive programming
ios_base::sync_with_stdio(false);
cin.tie(NULL);
int n, q;
if (!(cin >> n >> q)) return 0;
vector<int> a(n);
for (int i = 0; i < n; ++i) {
cin >> a[i];
}
// If max(a_i) is 20, and N is 10^5, the max possible answer is bounded by
// 20 + log2(10^5) ≈ 37. We use 40 as a safe upper bound.
const int MAX_COST = 40;
// jump[c][i] stores the rightmost index R we can reach starting from index i
// such that the subarray a[i...R-1] can be evaluated to a cost of <= c.
vector<vector<int>> jump(MAX_COST, vector<int>(n + 1, 0));
// Base Case Initialization
for (int c = 0; c < MAX_COST; ++c) {
for (int i = 0; i <= n; ++i) {
jump[c][i] = i; // With any cost, you can always cover an empty subarray
}
}
// Build the DP table bottom-up by cost
for (int c = 0; c < MAX_COST; ++c) {
for (int i = 0; i <= n; ++i) {
// Option 1: Inherit reach from a smaller cost
// If you can reach an index with cost c-1, you can reach it with cost c
if (c > 0) {
jump[c][i] = max(jump[c][i], jump[c - 1][i]);
}
// Option 2: A single element matches the target cost exactly
if (i < n && a[i] == c) {
jump[c][i] = max(jump[c][i], i + 1);
}
// Option 3: Merge two adjacent blocks of cost c-1
// A cost of c is formed by two brackets of cost c-1.
// So we jump with cost c-1 to a 'mid' point, and from there jump again with c-1.
if (c > 0) {
int mid = jump[c - 1][i];
jump[c][i] = max(jump[c][i], jump[c - 1][mid]);
}
}
}
// Process queries online
for (int i = 0; i < q; ++i) {
int L, R;
cin >> L >> R;
// Convert 1-based indexing from the problem input to 0-based indexing
--L;
--R;
int ans = 0;
// Find the smallest cost 'c' that allows us to cover the entire subarray [L...R]
for (int c = 0; c < MAX_COST; ++c) {
// If the furthest index we can reach starting from L is > R,
// it means we successfully covered the whole query segment.
if (jump[c][L] > R) {
ans = c;
break;
}
}
cout << ans << "\n";
}
return 0;
}
