#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define pll pair<long,long>
unordered_map<ll,ll> col_to_row;
vector<vector<ll>> row_to_col;
const int LOG = 19;
int jump[200005][LOG];
vector<vector<ll>> dp;
bool check(int mid, int row){
auto &curr_col = row_to_col[row];
auto &check_col = row_to_col[mid];
if (curr_col.empty() || check_col.empty()) return false;
for (auto x : curr_col){
for (auto y : check_col){
if (row + dp[x][1] >= mid - dp[y][0]) return true;
}
}
return false;
}
int main()
{
ios_base::sync_with_stdio(false);
cin.tie(NULL);
memset(jump, -1, sizeof(jump));
ll h, w; cin >> h >> w;
//0 = up, 1 = down
dp.resize(w+2, vector<ll>(2, 1));
row_to_col.resize(h+2);
for (ll i = 1; i < w+1; i++){
ll a; cin >> a; //row
row_to_col[a].emplace_back(i);
col_to_row[i] = a;
}
for (ll c = w; c > 0; c--){
ll curr_row = col_to_row[c];
auto &up_column = row_to_col[curr_row-1];
auto &down_column = row_to_col[curr_row+1];
//dp to find the maximum reach of each robot
for (auto ele: down_column){
if (ele <= c ) {dp[ele][0] += dp[c][0];}
}
for (auto ele: up_column){
if (ele <= c) {dp[ele][1] += dp[c][1];}
}
}
// for (ll i =1 ; i < w+1; i++){
// ll curr_row = col_to_row[i];
// cout << "Coor {" << curr_row << "," << i << "}";
// cout << " up: " << dp[i][0] << " down: " << dp[i][1] << endl;
// }
for (ll row = 1; row <= h; row++){
ll low = row, high = h;
ll ans = 0;
while (low <= high){
ll mid = low + (high-low)/2;
if (check(mid, row)){
ans = max(ans, mid);
low = mid +1;
}
else{
high = mid - 1;
}
}
//cout << ans << endl;
jump[row][0] = (ans == h? -1: ans+1);
}
for (ll k = 1; k < LOG; k++){
for (ll i = 1; i <= h; i++){
if (!(jump[i][k-1] == -1)){jump[i][k] = jump[jump[i][k-1]][k-1];}
}
}
// for (ll i = 1; i <= h; i++){
// cout << i << " : == > ";
// for (ll k = 0; k < LOG; k++){
// cout << jump[i][k] << " ";
// }
// cout << endl;
// }
ll q; cin >> q;
while (q--){
ll l, r; cin >> l >> r;
ll curr = l, ans = 0;
for (ll k = LOG-1; k >= 0; k--){
//cout << "steps: 2^" << k << " " << jump[curr][k] << endl;
if (!(jump[curr][k] == -1) and jump[curr][k] <= r){
curr = jump[curr][k];
ans += (1LL<<k);
}
}
cout << ans + 1 << "\n";
}
}
