#include<bits/stdc++.h>
#define int long long
#define endl '\n'
using namespace std;
const int N=1e5+10;
int n,q;
void solve()
{
    cin>>n>>q;
    vector<int>a(n),b(q),k(q);
    for(int i=0;i<n;i++)cin>>a[i];
    for(int i=0;i<q;i++)
    {
        cin>>b[i]>>k[i];
    }
    sort(a.begin(),a.end());
    //二分距离
    //如何使用upper和lower那就先二分距离，对b左右的距离的点在a中查看
    for(int i=0;i<q;i++)
    {
        int l=0,r=2e8,ans=0;
        while(l<=r)
        {
            int mid=l+r>>1;
            int l1=b[i]-mid;
            int r1=b[i]+mid;
            //[l1,r1]区间都满足到bi最近的点，有第k个正好
            int cnt=upper_bound(a.begin(),a.end(),r1)-lower_bound(a.begin(),a.end(),l1);
            if(cnt>=k[i])r=mid-1,ans=mid;
            else l=mid+1;
        }
        cout<<ans<<endl;
    }
}
signed main()
{
    ios::sync_with_stdio(false),cin.tie(0),cout.tie(0);
    int t=1;

    while(t--)solve();
    return 0;
}

D题的二分好想但我想不出如何实现，E题又看不出是dp