// WA

#include <algorithm>
#include <iostream>
#include <vector>
using namespace std;

vector<int> x;
vector<int> y;
int correct[202020];
int biggest[202020];
int smallest[202020];

int main(){
    ios::sync_with_stdio(0);
    cin.tie(0);
    int n, q;
    cin >> n >> q;

    for (int i=0; i<n; ++i){
        int a;
        cin >> a;
        x.push_back(a);
        y.push_back(a);
    }
    sort(y.begin(), y.end());

    if (x[0] == y[0]) correct[0] = 0;
    else correct[0] = -1;
    for (int i=1; i<n; ++i){
        if (x[i] == y[i]){
            if (correct[i-1] != -1) correct[i] = correct[i-1];
            else correct[i] = i;
        }
        else correct[i] = -1;
    }

    int big = 0;
    for (int i=0; i<n; ++i){
        big = max(x[i], big);
        biggest[i] = big;
    }

    int small = 1e9+1;
    for (int i=n-1; i>=0; --i){
        small = min(x[i], small);
        smallest[i] = small;
    }

    for (int i=1; i<=q; ++i){
        int a, b;
        cin >> a >> b;
        bool ok = true;
        if (biggest[a-1] > y[a-1]) ok = false;
        if (smallest[n-b] < y[n-b]) ok = false;
        if (n-b > a){
            if (correct[n-b-1] == -1 || correct[n-b-1] > a+1) ok = false;
        }
        //cout << n << " " << a << " " << b << " " << correct[n-b-1] << " \n";
        if (ok == false) {
            cout << "-1\n";
            continue;
        }
        int ans = 0;
        if (correct[a-1] != 0) ans++;
        if (correct[n-1] == -1 || correct[n-1] > n-b) ans++;
        cout << ans << "\n";
    }


}
