#include <fstream>

using namespace std;

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

int n,m, v[100001];

int cautbin(int nr){

    int left = 1;
    int right = n;
    while(left<right){
        int pivot = (left + right)/2;

        if(v[pivot]<nr)
            left = pivot + 1;
        else if(v[pivot]>nr)
            right = pivot - 1;
        else return pivot;


    }

    return left;
}

int main(){
    fin>>n;
    for(int i=1;i<=n;++i)
        fin>>v[i];

    fin>>m;
    while(m--){
        int op, x;
        fin>>op>>x;

        int pos = cautbin(x);
        
        if(op == 0){
            
            if(v[pos] == x){
                while(v[pos] == x && pos<=n)++pos;
                fout<<pos-1<<'\n';

            }
            else fout<<-1<<'\n';

        }
        else if( op == 1)
        {

            if(v[pos] <= x)
            {
                while(v[pos] <= x && pos <= n)++pos;
                fout<<pos-1<<'\n';
            }else{
                while(v[pos] > x && pos>0)--pos;
                fout<<pos<<'\n';
            }
        }
        else if( op == 2){
            if(v[pos] >= x)
            {
                while(v[pos] >= x && pos > 0)--pos;
                fout<<pos+1<<'\n';
            }
            else{
                while(v[pos] < x && pos<=n)++pos;
                fout<<pos<<'\n';
            }


        }

    }




    return 0;
}