#include <fstream>

using namespace std;
ifstream cin("cautbin.in");
ofstream cout("cautbin.out");
int main()
{
    int p,x,n,m,i,dr,st,mij;
    cin>>n;
    int v[n+1];
    for(i=1;i<=n;i++)
        cin>>v[i];
    cin>>m;
    while(m)
    {
        cin>>p>>x;
        st=1;dr=n;
        if(p==0)
        {
            if(v[n]<x||v[1]>x)cout<<-1;
            else
                while(st<=dr)
                {
                    mij=(st+dr)/2;
                    if(v[mij]<x)st=mij;
                    else if(v[mij]>x)dr=mij;
                    else
                    {
                        if(v[mij+1]==x)st=mij;
                        else {cout<<mij;break;}
                    }
                }
        }
        else if(p==1)
        while(st<=dr)
        {
            mij=(st+dr)/2;
            if(v[mij]<=x&&v[mij+1]>x){cout<<mij;break;}
            else if(v[mij]<=x&&v[mij+1]<=x)st=mij;
            else if(v[mij]>x)dr=mij;
        }
        else
            while(st<=dr)
        {
            mij=(st+dr)/2;
            if(v[mij]>=x&&v[mij-1]<x){cout<<mij;break;}
            else if(v[mij]>=x&&v[mij-1]>=x)dr=mij;
            else if(v[mij]<x)st=mij;
        }
    }
    return 0;
}