// Subtasks:
// 7: AC/TLE
// _: AC

// TODO: Design a slower test for this?

#include <algorithm>
#include <iostream>
#include <map>
#include <vector>

using namespace std;

int divide_up(int a, int b) {
    return (a+b-1)/b;
}

#define N (1<<18)
vector<int> tree[2*N];

int tree_count(int a, int b, int x) {
    a += N; b += N;
    int c = 0;
    while (a <= b) {
        if (a%2 == 1) {
            auto it = lower_bound(tree[a].begin(), tree[a].end(), x);
            c += tree[a].end() - it;
            a++;
        }
        if (b%2 == 0) {
            auto it = lower_bound(tree[b].begin(), tree[b].end(), x);
            c += tree[b].end() - it;
            b--;
        }
        a /= 2; b /= 2;
    }
    return c;
}

int main() {
    ios_base::sync_with_stdio(0);
    cin.tie(0);

    int n, q;
    cin >> n >> q;
    vector<pair<int,int>> pairs(n);
    for (int i = 0; i < n; i++) {
        cin >> pairs[i].first;
        pairs[i].second = i;
    }
    vector<pair<int,int>> sorted = pairs;
    sort(sorted.begin(), sorted.end());
    map<pair<int,int>,int> label;
    for (int i = 0; i < n; i++) {
        label[sorted[i]] = i;
    }
    vector<int> values(n);
    for (int i = 0; i < n; i++) {
        values[i] = label[pairs[i]];
    }

    vector<int> errors(n);
    int error_total = 0;
    for (int i = 0; i < n; i++) {
        errors[i] = values[i] != i;
        error_total += errors[i];
    }

    vector<int> min_left(n), max_left(n), error_left(n);
    min_left[0] = values[0];
    max_left[0] = values[0];
    error_left[0] = errors[0];
    for (int i = 1; i < n; i++) {
        min_left[i] = min(min_left[i-1], values[i]);
        max_left[i] = max(max_left[i-1], values[i]);
        error_left[i] = error_left[i-1] + errors[i];
    }

    vector<int> min_right(n), max_right(n), error_right(n);
    min_right[n-1] = values[n-1];
    max_right[n-1] = values[n-1];
    error_right[n-1] = errors[n-1];
    for (int i = n-2; i >= 0; i--) {
        min_right[i] = min(min_right[i+1], values[i]);
        max_right[i] = max(max_right[i+1], values[i]);
        error_right[i] = error_right[i+1] + errors[i];
    }

    for (int i = 0; i < n; i++) {
        tree[N+i] = {values[i]};
    }
    for (int i = N-1; i >= 1; i--) {
        merge(tree[2*i].begin(), tree[2*i].end(),
              tree[2*i+1].begin(), tree[2*i+1].end(),
              back_inserter(tree[i]));
    }

    for (int i = 1; i <= q; i++) {
        int a, b;
        cin >> a >> b;
        if (a+b <= n) {
            bool fail = false;
            if (error_left[a-1] + error_right[n-b] < error_total) fail = true;
            if (a != n && max_left[a-1] > min_right[a]) fail = true;
            if (b != n && min_right[n-b] < max_left[n-b-1]) fail = true;
            if (fail) {
                cout << "-1\n";
            } else {
                int ans = 0;
                if (error_left[a-1]) ans++;
                if (error_right[n-b]) ans++;
                cout << ans << "\n";
            }
        } else if (a == n || b == n || error_left[n-1] == 0) {
            cout << (error_left[n-1] != 0) << "\n";
        } else {
            int left_to_right = tree_count(0, n-b-1, a);
            int middle_to_left = (a-(n-b)) - tree_count(n-b, a-1, n-b);
            int middle_to_right = tree_count(n-b, a-1, a);
            int right_to_left = (n-a) - tree_count(a, n-1, n-b);
            int window = a+b-n;
            bool sort_left = error_left[n-b-1] > 0;
            bool sort_right = error_right[a] > 0;
            int left_ops = 0;
            {
                int left_move = divide_up(left_to_right + middle_to_right, window);
                int right_move = divide_up(right_to_left, window);
                if (left_move > right_move) {
                    left_ops = 2 * left_move;
                } else {
                    left_ops = 2 * right_move + 1;
                }
                if (sort_left) left_ops = max(left_ops, 1);
                if (sort_right) left_ops = max(left_ops, 2);
            }
            int right_ops = 0;
            {
                int left_move = divide_up(left_to_right, window);
                int right_move = divide_up(right_to_left + middle_to_left, window);
                if (right_move > left_move) {
                    right_ops = 2 * right_move;
                } else {
                    right_ops = 2 * left_move + 1;
                }
                if (sort_right) right_ops = max(right_ops, 1);
                if (sort_left) right_ops = max(right_ops, 2);
            }
            int ops = min(left_ops, right_ops);
            cout << ops << "\n";
        }
    }
}
