#include <cstdio>
#include <algorithm>
using namespace std;

struct Node {
    int sum;
    Node *lc, *rc;
    Node(int s);
    Node(Node*, Node*);
};

Node::Node(int s) : sum(s), lc(nullptr), rc(nullptr) {}
Node::Node(Node *l, Node *r) : sum(l->sum + r->sum), lc(l), rc(r) {}

Node* create(int l, int r) {
    if(l + 1 == r)
        return new Node(0);
    else
        return new Node(create(l, (l + r) / 2), create((l + r) / 2, r));
}

int sum(Node *n, int r, int nl, int nr) {
    if(nr <= r)
        return n->sum;
    else if(r > nl)
        return sum(n->lc, r, nl, (nl + nr) / 2) +
               sum(n->rc, r, (nl + nr) / 2, nr);
    else
        return 0;
}

Node* increase(Node *n, int x, int nl, int nr) {
    if(nl + 1 == nr)
        return new Node(n->sum + 1);
    else if(x < (nl + nr) / 2)
        return new Node(increase(n->lc, x, nl, (nl + nr) / 2), n->rc);
    else
        return new Node(n->lc, increase(n->rc, x, (nl + nr) / 2, nr));
}

Node* nodes[100001];

bool ok(int n, int p, int k, int s) {
    return sum(nodes[min(p + s + 1, n)], s, 0, n) -
           sum(nodes[max(p - s    , 0)], s, 0, n) >= k;
}

int main(){
    int n, m;
    scanf("%d %d", &n, &m);
    nodes[0] = create(0, n);
    for(int i = 0; i < n; i++) {
        int b;
        scanf("%d", &b);
        b--;
        nodes[i + 1] = increase(nodes[i], b, 0, n);
    }
    for(int i = 0; i < m; i++) {
        int p, k;
        scanf("%d %d", &p, &k);
        int l = 0, r = n;
        while(l < r) {
            int s = (l + r) / 2;
            ok(n, p, k, s) ? (r = s) : (l = s + 1);
        }
        printf("%d\n", r);
    }
}