// Subtasks:
// 1: AC
// 2: AC
// _: WA/TLE


#include <algorithm>
#include <iostream>
#include <vector>
 
using namespace std;
 
bool ready(vector<int> &v, int n) {
    for (int i = 2; i <= n; i++) {
        if (v[i] < v[i-1]) return false;
    }
    return true;
}
 
int calc(vector<int> v, int n, int a, int b, int f) {
    int c = 0;
    int r = 0;
    vector<int> zf(n+1);
    vector<int> zc(n+1);
    int g = 0;
    while (true) {
        if (ready(v, n)) return c;
        auto u = v;
        r++;
        if (f == 1) {
            for (int i = 1; i <= a; i++) {
                if (zf[v[i]] != r) {
                    zf[v[i]] = r;
                    zc[v[i]] = 1;
                } else {
                    zc[v[i]]++;
                }
            }
            int j = 1;
            for (int i = 1; i <= n && j <= a; i++) {
                while (zf[i] == r && zc[i]) {
                    v[j++] = i;
                    zc[i]--;
                }
            }
        }
        if (f == 2) {
            for (int i = n-b+1; i <= n; i++) {
                if (zf[v[i]] != r) {
                    zf[v[i]] = r;
                    zc[v[i]] = 1;
                } else {
                    zc[v[i]]++;
                }
            }
            int j = n-b+1;
            for (int i = 1; i <= n && j <= n; i++) {
                while (zf[i] == r && zc[i]) {
                    v[j++] = i;
                    zc[i]--;
                }
            }
        }
        f = 3-f;
        c++;
        if (u == v) g++;
        else g = 0;
        if (g > 2) return 1e9;
    }
}
 
int main() {
    int n, q;
    cin >> n >> q;
    vector<int> v(n+1);
    vector<pair<int,int>> vs;
    for (int i = 1; i <= n; i++) {
        cin >> v[i];
        vs.push_back({v[i],i});
    }
    sort(vs.begin(), vs.end());
    int lc = 0;
    int lv = 0;
    for (int i = 0; i < n; i++) {
        if (vs[i].first != lv) {
            lv = vs[i].first;
            lc++;
        }
        v[vs[i].second] = lc;
    }
    for (int i = 1; i <= q; i++) {
        int a, b;
        cin >> a >> b;
        int c1 = calc(v, n, a, b, 1);
        int c2 = calc(v, n, a, b, 2);
        int r = min(c1, c2);
        if (r == 1e9) r = -1;
        cout << r << "\n";
    }
 
}
