#include <fstream>

using namespace std;

int binkereses0(int n, int t[], int x)
{
    int eredmeny=-1;
    int bal=1, jobb=n;
    while(bal<=jobb){
        int kozep=(bal+jobb)/2;
        if (t[kozep]==x){
            eredmeny=kozep;
            bal=kozep+1;
        }
        else if(t[kozep]<x){
            bal=kozep+1;
        }else{
            jobb=kozep-1;
        }
    }

    return eredmeny;
}

int binkereses1(int n, int t[], int x)
{
    int eredmeny=-1;
    int bal=1, jobb=n;
    while(bal<=jobb){
        int kozep=(bal+jobb)/2;
        if (t[kozep]<=x){
            eredmeny=kozep;
            bal=kozep+1;
        }else{
            jobb=kozep-1;
        }
    }

    return eredmeny;
}

int binkereses2(int n, int t[], int x)
{
    int eredmeny=-1;
    int bal=1, jobb=n;
    while(bal<=jobb){
        int kozep=(bal+jobb)/2;
        if (t[kozep]>=x){
            eredmeny=kozep;
            jobb=kozep-1;
        }
        else if(t[kozep]<x){
            bal=kozep+1;
        }
    }

    return eredmeny;
}

int main()
{

    ifstream be("cautbin.in");
    ofstream ki("cautbin.out");

    int n;
    be>>n;
    int t[100001];
    for(int i=1; i<=n; i++){
        be>>t[i];
    }
    int m;
    be>>m;
    int tipus;
    int x;
    for(int i=1; i<=m; i++){
        be>>tipus>>x;
        if(tipus==0){
            ki<<binkereses0(n, t, x)<<endl;
        }else if(tipus==1){
            ki<<binkereses1(n, t, x)<<endl;
        }else{
            ki<<binkereses2(n, t, x)<<endl;
        }
    }


    return 0;
}