#include<stdio.h>

#define Nmax 100010

int N,S[Nmax];

int caut_mic(int x)
{
    int st,dr,mid,first=0;

    for(st=1,dr=N;st<=dr;)
        {
        mid=st+(dr-st)/2;
        if (x >= S[mid])
            {
            st=mid+1;
            first=mid;
            }
        else
            dr=mid-1;
        }
    return first;
}

int caut_mare(int x)
{
    int st,dr,last=N,mid;

    for(st=1,dr=N;st<=dr;)
        {
        mid=st+(dr-st)/2;
        if (x <= S[mid])
            {
            dr=mid-1;
            last=mid;
            }
        else
            st=mid+1;
        }
    return last;
}

int caut_fix(int x)
{
    int poz=caut_mic(x);
    if (S[poz]==x)
        return poz;
    return -1;
}

int main()
{
    int M,x,y;
    freopen("cautbin.in","r",stdin);
    freopen("cautbin.out","w",stdout);
    scanf("%d",&N);
    for(int i=1;i<=N;++i)
        scanf("%d ",&S[i]);
    scanf("%d",&M);
    for(int i=1;i<=M;++i)
        {
        scanf("%d%d",&x,&y);
        if (x==0)
            printf("%d\n",caut_fix(y));
        if (x==1)
            printf("%d\n",caut_mic(y));
        if (x==2)
            printf("%d\n",caut_mare(y));
        }
    return 0;
}