#include <cstdio>

using namespace std;

int main()
{
    freopen("cautbin.in","r",stdin);
    freopen("cautbin.out","w",stdout);
    int n,v[100005],m,t,val;
    scanf("%d",&n);
    for(int i=1;i<=n;i++)
    {
        scanf("%d",&v[i]);
    }
    scanf("%d",&m);
    for(int i=1;i<=m;i++)
    {
        scanf("%d%d",&t,&val);
        if(t==0)
        {
            int st=1,dr=n,mij;
            while(st<=dr)
            {
                mij=(st+dr)/2;
                if(v[mij]>val)
                    dr=mij-1;
                else
                    st=mij+1;
            }
            int rasp=(st+dr)/2;
            if(v[rasp]>val)
                rasp--;
            if(v[rasp]==val)
                printf("%d\n",rasp);
            else
                printf("-1\n");
        }
        if(t==1)
        {
            int st=1,dr=n,mij;
            while(st<dr)
            {
                mij=(st+dr)/2;
                if(v[mij]>val)
                    dr=mij;
                else
                    st=mij+1;
            }
            mij=(st+dr)/2;
            if(v[mij]>val)
                mij--;
            printf("%d\n",mij);
        }
        if(t==2)
        {
            int st=1,dr=n,mij;
            while(st<dr)
            {
                mij=(st+dr)/2;
                if(v[mij]>=val)
                    dr=mij;
                else
                    st=mij+1;
            }
            mij=(st+dr)/2;
            if(v[m]<val)
                m++;
            printf("%d\n",mij);
        }
    }
    return 0;
}