#include<cstdio>
#define mare 100001
int a[mare],b[mare],c[mare],x,y,i,j,n,m,k,mij;
int bin(int x,int &y,int &k,int &nr)
{
    mij=(x+y)/2;
    if(x>y) return -1;
    if(k==0)
    {
      if(a[mij]==nr&&a[mij+1]!=nr)
            return mij;
    if(nr>=a[mij])
            return bin(mij,y,k,nr);
       if(nr<a[mij])
            return bin(x,mij,k,nr);
    }
    if(k==1)
    {
        if(a[mij]<=nr&&a[mij+1]>nr)
            return mij;
        if(nr>=a[mij])
            return bin(mij,y,k,nr);
       if(nr<a[mij])
            return bin(x,mij,k,nr);
    }
    if(k==2)
    {
        if(a[mij]>=nr&&a[mij-1]<nr)
            return mij;
        if(nr>a[mij])
            return bin(mij,y,k,nr);
       if(nr<=a[mij])
            return bin(x,mij,k,nr);
    }

return 0;

}
using namespace std;

int main()
{
    freopen("cautbin.in","r",stdin);
    freopen("cautbin.out","w",stdout);
    scanf("%d",&n);
    for(i=1;i<=n;i++)
        scanf("%d",&a[i]);
    scanf("%d",&m);
    for(i=1;i<=m;i++)
    scanf("%d %d",&b[i],&c[i]);
    for(i=1;i<=m;i++)

    printf("%d\n",bin(1,n,b[i],c[i]));

    return 0;
}