#include<cstdio>
using namespace std;
int m,ls,ld,i,n,intr,x,mij,v[100001];
int main()
{
    freopen("cautbin.in","r",stdin);
    freopen("cautbin.out","w",stdout);
    scanf("%d",&n);
    for(i=1;i<=n;i++)
        scanf("%d",&v[i]);
    scanf("%d",&m);
    for(i=1;i<=m;i++)
    {
        scanf("%d %d",&intr,&x);
        if(intr==0)
        {
            ls=1;
            ld=n;
            while(ls<=ld)
            {
                mij=(ls+ld)/2;
                if(v[mij]<=x)
                    ls=mij+1;
                else
                    ld=mij-1;
            }
            if(v[ld]==x)
                printf("%d\n",ld);
            else
                if(v[ld]!=x)
                    printf("-1\n");
        }
        else
            if(intr==1)
                printf("%d\n",ld);
            else
            {
                ls=1;
                ld=n;
                mij=(ls+ld)/2;
                while(ls<=ld)
                {
                    mij=(ls+ld)/2;
                    if(v[mij]>=x)
                        ld=mij-1;
                    else
                        ls=mij+1;
                }
                printf("%d",ls);
            }
    }
    return 0;
}