#include <iostream>
#include <cstdio>

FILE *f,*g;
using namespace std;

int binary_search0 (long V[100001], long left, long right, long x)
{
    long mij;
    while(left<=right)
    {
        mij=(left+right)/2;
        if(V[mij]<=x)
            left=mij+1;
        else
            right=mij-1;
    }
    mij=(left+right)/2;
    if(V[mij]>x)
        mij--;
    if(V[mij]==x)
        return mij;
    return -1;
}

int binary_search1 (long V[100001], long left, long right, long x)
{
    long mij;
    while(left<right)
    {
        mij=(left+right)/2;
        if(V[mij]<=x)
            left=mij+1;
        else
            right=mij;
    }
    mij=(left+right)/2;
    if(V[mij]>x)
        mij--;
    return mij;
}

int binary_search2 (long V[100001], long left, long right, long x)
{
    long mij;
    while(left<right)
    {
        mij=(left+right)/2;
        if(V[mij]<x)
            left=mij+1;
        else
            right=mij;
    }
    mij=(left+right)/2;
    if(V[mij]<x)
        mij++;
    return mij;
}

int main(){
f=fopen("cautbin.in","r");
g=fopen("cautbin.out","w");
long i,N,M,A[100001],x,k;
int b;
fscanf(f,"%ld",&N);
for(i=1;i<=N;i++)
{
    fscanf(f,"%ld",&A[i]);
}
fscanf(f,"%ld",&M);
for(i=1;i<=M;i++)
{
    fscanf(f,"%d%ld",&b,&x);
    if(b==0)
    {
        k=binary_search0(A,1,N,x);
        fprintf(g,"%ld\n",k);
    }
    if(b==1)
    {
        k=binary_search1(A,1,N,x);
        fprintf(g,"%ld\n",k);
    }
    if(b==2)
    {
        k=binary_search2(A,1,N,x);
        fprintf(g,"%ld\n",k);
    }
}
fclose(f);
fclose(g);
return 0;
}