#include <bits/stdc++.h>

using namespace std;

ifstream fin("cautbin.in");
ofstream fout("cautbin.out");

long long n,i,v[100001],m,c,x;

int maco0(){
    int st=0,dr=n-1;
    int mij=(st+dr)/2;
    while(st<=dr){
        mij=(st+dr)/2;
        if(v[mij]==x){
            while(v[mij]==x) mij++;
            mij--;
            return mij;
        }
        else if(v[mij]<x) st=mij+1;
        else dr=mij-1;
    }
    return -2;
}
int maco1(){
    int st=0,dr=n-1;
    int mij=(st+dr)/2;
    while(st<=dr){
        mij=(st+dr)/2;
        if(v[mij]==x){
            while(v[mij]==x) ++mij;
            --mij;
            return mij;
        }
        else if(v[mij]<x) st=mij+1;
        else dr=mij-1;
    }
    while(v[mij]>x) --mij;
    return mij;
}
int maco2(){
    int st=0,dr=n-1;
    int mij=(st+dr)/2;
    while(st<=dr){
        mij=(st+dr)/2;
        if(v[mij]==x){
            while(v[mij]==x) --mij;
            ++mij;
            return mij;
        }
        else if(v[mij]<x) st=mij+1;
        else dr=mij-1;
    }
    while(v[mij]<x) ++mij;
    return mij;
}

int main()
{
    fin>>n;
    for(i=0;i<n;++i) fin>>v[i];
    fin>>m;
    for(i=0;i<m;++i){
        fin>>c>>x;
        long long rasp;
        if(c==0) rasp=maco0();
        else if(c==1) rasp=maco1();
        else rasp=maco2();
        fout<<rasp+1<<'\n';
    }
    return 0;
}