#include <cstdlib>
#include <fstream>
#include<iostream>
#include <math.h>
using namespace std;

#define BIG 100005
int v[BIG],n,rasp=-1;


void cautare_binara(int v[],int val, int caz){
    int st = 0, dr = n-1, mij;
    rasp = -1;
    while(st<=dr){
        mij = st +floor((dr - st)/2);

        if(v[mij] < val)
            st = mij+1;
        else if(v[mij] > val)
            dr = mij-1;
        else {
            rasp = mij;
            break;
        }
    }

    if(caz == 0){
        if(rasp != -1){
            while(v[mij] == val)
                mij++;
        rasp = mij  ;
        }}
    else if(caz == 1){
        
        if(rasp == -1)
            cautare_binara(v,v[mij-1],0);
        else{
             while(v[rasp] == val)
                rasp ++;
        }
    }
    else{
      
         if(rasp != -1){
            while(v[mij] == val){
                mij--;
            }
         rasp = mij+2;}
         else cautare_binara(v,v[mij+1],2);
    }
}

int main() {
    int i,m,caz,val;
    ifstream fin("cautbin.in");
    ofstream fout("cautbin.out");
    fin>>n;
    for(i=0;i<n;++i)
        fin>>v[i];
    fin>>m;
    for(i = 0;i<m;++i){
        fin>>caz>>val;
        cautare_binara(v,val,caz);
        fout<<rasp<<"\n";
    }
        
    return 0;
}