#include <stdio.h>
#define Nmax 110001
 
int N,M,x,y,m,r;
int v[Nmax];
void cauta0(int a,int b,int m)
{
        while(a<=b)
            {
                    m=(a+b)/2;
                    if(v[m]<x)
                            a=m+1;
                    else
                            b=m-1;
                }
        if(v[m]==x)
            {
                    printf("%d\n",m);
                    return;
                }
        printf("-1\n");
}
void cauta1(int a,int b,int x)
{
        while(a<b)
            {
                    m=(a+b)/2;
                    if (v[m]<x)
                            a=m+1;
                    else
                            b=m;
                }
        m=(a+b)/2;
        if (v[m]>x)
                --m;
        printf("%d\n", m);
}
void cauta2(int a,int b,int m)
{
        while(a<b)
            {
                    m=(a+b)/2;
                    if (v[m]<x)
                            a=m+1;
                    else
                            b=m;
                }
        m=(a+b)/2;
        if (v[m]<x)
                ++m;
        printf("%d\n", m);
}
int main()
{
        freopen("cautbin.in", "r",stdin);
        freopen("cautbin.out", "w",stdout);
        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", &y,&x);
                    switch(y)
                    {
                                case 0: { cauta0(1,N,x); break;}
                                case 1: { cauta1(1,N,x); break;}
                                case 2: { cauta2(1,N,x); break;}
                        }   
                }   
        return 0;
}