#include <iostream>
#include <algorithm>
#include <fstream>
using namespace std;
ifstream f("cautbin.in");
ofstream g("cautbin.out");
int i,j,n,v[100001],a,x,M;
bool ok;
int b0(int i, int j, int x){
     int m, t=-1;
     while(i<=j) {
        m=(i+j)/2;
        if(x==v[m]) {
            t=m;
            i=m+1;
        }
        else if (x <v[m]) j = m-1;
        else i=m+1;
    }
    return t;
}
int b1(int i, int j, int x){
     int m,t;
     while(i<=j) {
        m=(i+j)/2;
        if(v[m]<=x) {
            t=m;
            i=m+1;
        }
        else j=m-1;
    }
    return t;
}
int b2(int i, int j, int x){
     int m,t;
     while(i<=j) {
        m=(i+j)/2;
        if(v[m]>=x) {
            t=m;
            j=m-1;
        }
        else i=m+1;
    }
    return t;
}
int main()
{
    f>>n;
    for(i=1;i<=n;++i) f>>v[i];
    f>>M;
    for(i=1;i<=M;i++){
        f>>a>>x;
        if(a==0) g<<b0(1,n,x)<<"\n";
        else if(a==1) g<<b1(1,n,x)<<"\n";
        else g<<b2(1,n,x)<<"\n";
    }
    return 0;
}