#include<cstdio>
using namespace std;
int m,ls,ld,i,n,intr,x,mij,cp,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;
                if(v[mij]>x)
                    ld=mij-1;
                else break;
            }
            if(v[mij]==x)
            {
                while(v[mij]==x) mij++;
                mij--;
                printf("%d\n",mij);
            }
            else printf("-1\n");
        }
        else
        if(intr==1)
        {
            ls=1;
            ld=n;
            while(ls<=ld)
            {
                mij=(ls+ld)/2;
                if(v[mij]<x)
                    ls=mij+1;
                if(v[mij]>x)
                    ld=mij-1;
                else break;
            }
            if(v[mij]==x)
            {
                while(v[mij]==x) mij++;
                mij--;
                printf("%d\n",mij);
            }
            else
            {
                mij=ls;
                while(v[mij]>x) mij--;
                printf("%d\n",mij);
            }
        }
        else
        {
            ls=1;
            ld=n;
            while(ls<=ld)
            {
                mij=(ls+ld)/2;
                if(v[mij]<x)
                    ls=mij+1;
                if(v[mij]>x)
                    ld=mij-1;
                else break;
            }
            if(v[mij]==x)
            {
                while(v[mij]==x) mij--;
                mij++;
                printf("%d\n",mij);
            }
            else
            {
                mij=ls;
                while(v[mij]<x) mij++;
                printf("%d\n",mij);
            }
        }
    }
    return 0;
}