#include <fstream>
#define DIM 100002
using namespace std;

ifstream fin("cautbin.in");
ofstream fout("cautbin.out");
int n,i,v[DIM],m,op,j;
int cautbin0(int x){
    int p=1,u=n,mid,maxim=-1;
    while(p<=u){
        mid=p+(u-p)/2;
        if(v[mid]<x)
            p=mid+1;
        else {
            if(v[mid]>x)
                u=mid-1;
            else
                break;
        }

    }
    if(v[mid]!=x)
        return -1;
    while(v[mid]==x)
        mid++;
    return --mid;
}
int cautbin1(int x){
    int p=1,u=n,mid,maxim=-1;
    while(p<=u){
        mid=p+(u-p)/2;
        if(v[mid]<x)
            p=mid+1;
        else {
            if(v[mid]>x)
                u=mid-1;
            else
                break;
        }

    }
    while(v[mid]<=x && mid<=n)
        mid++;
    return --mid;
}
int cautbin2(int x){
    int p=1,u=n,mid,maxim=-1;
    while(p<=u){
        mid=p+(u-p)/2;
        if(v[mid]<x)
            p=mid+1;
        else {
            if(v[mid]>x)
                u=mid-1;
            else
                break;
        }

    }
    while(v[mid]>=x && mid>=1)
        mid--;
    return ++mid;
}
int main(){
    fin>>n;
    for(i=1;i<=n;i++)
        fin>>v[i];
    fin>>m;
    while(m--){
        fin>>op>>j;
        if(op==0)
            fout<<cautbin0(j)<<"\n";
        if(op==1)
            fout<<cautbin1(j)<<"\n";
        if(op==2)
            fout<<cautbin2(j)<<"\n";
    }
    fin.close();fout.close();
    return 0;
}