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

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

using namespace std;
using ll = long long;

int main() {
    cin.tie(0) -> sync_with_stdio(0);

    int n, q;
    cin >> n >> q;

    vector<int> x(n);
    for (int &i : x) cin >> i;

    auto y = x;
    sort(y.begin(), y.end());

    for (int i = 0; i < q; ++i) {
        int a, b;
        cin >> a >> b;

        int ans = 1e9;
        if (a+b <= n) {
            if (x == y) ans = 0;
            auto z = x;
            sort(z.begin(), z.begin()+a);
            if (z == y) ans = min(ans, 1);
            z = x;
            sort(z.end()-b, z.end());
            if (z == y) ans = min(ans, 1);
            sort(z.begin(), z.begin()+a);
            if (z == y) ans = min(ans, 2);
            if (ans == 1e9) ans = -1;
        } else {
            auto z = x;
            int j;
            for (j = 0; z != y; ++j) {
                if (j & 1) sort(z.begin(), z.begin()+a);
                else sort(z.end()-b, z.end());
            }
            ans = min(ans, j);
            z = x;
            for (j = 0; z != y; ++j) {
                if (j & 1) sort(z.end()-b, z.end());
                else sort(z.begin(), z.begin()+a);
            }
            ans = min(ans, j);
        }
        cout << ans << '\n';
    }

    return 0;
}
