#include <iostream>
#include <fstream>
using namespace std;
int cautare_0(int v[100001],int s,int d,int x){
    int m;
    while(s<d){
        m=s+(d-s)/2;
        if(v[m]<=x)
            s=m+1;
        else
            d=m-1;
    }
    if(v[s]>x)
        s--;
    if(v[s]==x)
        return s;
    return -1;
}
int cautare_1(int v[100001],int s,int d,int x){
    int m;
    while(s<d){
        m=s+(d-s)/2;
        if(v[m]<=x)
            s=m+1;
        else
            d=m;
    }
    if(v[s]>x)
        s--;
    return s;
}
int cautare_2(int v[100001],int s,int d,int x){
    int m;
    while(s<d){
        m=s+(d-s)/2;
        if(v[m]>=x)
            d=m;
        else
            s=m+1;
    }
    if(v[s]<x)
        s++;
    return s;
}
int main(){
    ifstream f("cautbin.in");
    ofstream g("cautbin.out");
    int v[100001],n,x,m,k,i;
    f>>n;
    for(i=1;i<=n;i++)
        f>>v[i];
    f>>m;
    for(i=1;i<=m;i++){
        f>>k>>x;
        if(k==0)
            g<<cautare_0(v,1,n,x)<<endl;
        if(k==1)
            g<<cautare_1(v,1,n,x)<<endl;
        if(k==2)
            g<<cautare_2(v,1,n,x)<<endl;
    }
    f.close();
    g.close();
    return 0;
}