#include <cstdio>
int n,m;
int a[100001];
int main()
{
    freopen ("cautbin.in","r",stdin);
    freopen ("cautbin.out","w",stdout);
    scanf("%d",&n);
    for(int i=1;i<=n;i++) scanf("%d",&a[i]);
    int tip,nr;
    scanf("%d",&m);
    for(int x=1;x<=m;x++)
    {
        scanf("%d%d",&tip,&nr);
        if(tip==0)
        {
            int pos=-1,s=1,e=n;
            while(s<=e)
            {
                int mij=(s+e)/2;
                if(a[mij]==nr)
                {
                    pos=mij;
                    s=mij+1;
                }
                else if(a[mij]<nr) s=mij+1;
                else e=mij-1;
            }
            printf("%d\n",pos);
        }
        else if(tip==1)
        {
            int pos,s=1,e=n;
            while(s<=e)
            {
                int mij=(s+e)/2;
                if(a[mij]<=nr)
                {
                    pos=mij;
                    s=mij+1;
                }
                else e=mij-1;
            }
            printf("%d\n",pos);
        }
        else if(tip==2)
        {
            int pos,s=1,e=n;
            while(s<=e)
            {
                int mij=(s+e)/2;
                if(a[mij]>=nr)
                {
                    pos=mij;
                    e=mij-1;
                }
                else s=mij+1;
            }
            printf("%d\n",pos);
        }
    }
}