#include <fstream>

using namespace std;
ifstream fin("cautbin.in");
ofstream fout("cautbin.out");
const int nmax=100000;
int x[nmax+5],n,m;
int binarysearch(int value){
    int sol=-1;
    int left=1, right=n;
    while(left<=right){
        int mid=(left+right)/2;
        if(x[mid]==value){
            sol=mid;
            left=mid+1;
        }
        else
            if(x[mid]<value)
                left=mid+1;
            else
                right=mid-1;
    }
    return sol;
}
int binarysearch1(int value){
    int sol;
    int left=1, right=n;
    while(left<=right){
        int mid=(left+right)/2;
        if(x[mid]<=value){
            sol=mid;
            left=mid+1;
        }
        else
            right=mid-1;
    }
    return sol;
}
int binarysearch2(int value){
    int sol=-1;
    int left=1, right=n;
    while(left<=right){
        int mid=(left+right)/2;
        if(x[mid]>=value){
            sol=mid;
            right=mid-1;
        }
        else
            left=mid+1;
    }
    return sol;
}
int main()
{
    fin>>n;
    for(int i=1;i<=n;i++)
        fin>>x[i];
    fin>>m;
    while(m--){
        int op,y;
        fin>>op>>y;
        if(op==0)
            fout<<binarysearch(y)<<"\n";
        if(op==1)
            fout<<binarysearch1(y)<<"\n";
        if(op==2)
            fout<<binarysearch2(y)<<"\n";
    }
    return 0;
}