#include <fstream>

using namespace std;
ifstream cin("cautbin.in");
ofstream cout("cautbin.out");

int n,i,f,c,x,a[100001],st,dr,poz,m;
int main()
{
    cin>>n;
    for(i=1;i<=n;i++)
        cin>>a[i];
    cin>>f;
    for(i=1;i<=f;i++)
    {
        cin>>c>>x;
        if(c==0)
        {
            st=1,dr=n,poz=-1;
            while(st<=dr)
            {
                m=(st+dr)/2;
                if(a[m]==x) poz=m,st=m+1;
                else dr=m-1;
            }
            cout<<poz<<'\n';
        }
        if(c==1)
        {
            st=1,dr=n,poz=-1;
            while(st<=dr)
            {
                m=(st+dr)/2;
                if(a[m]<=x){poz=m,st=m+1;}
                else dr=m-1;
            }
            cout<<poz<<'\n';
        }
        if(c==2)
        {
            st=1;dr=n;poz=-1;
            while(st<=dr)
            {
                m=(st+dr)/2;
                if(a[m]>=x){poz=m; dr=m-1;}
                else st=m+1;
            }
            cout<<poz<<'\n';
        }
    }
    return 0;
}