#include <iostream>
#include <fstream>

using namespace std;
int v[100005];
ifstream fin("cautbin.in");
ofstream fout("cautbin.out");

int cautbin1(int st, int dr, int x, int type){
    int ans=-1;
    while(st<=dr){
      int med=(st+dr)/2;
      if(v[med]<=x){
        ans=med;
        st=med+1;
      }else{
        dr=med-1;
      }

    }
    if(type==0 && v[ans]!=x)
        return -1;
    else return ans;
}
int cautbin2(int st, int dr, int x){
    int ans=-1;
    while(st<=dr){
      int med=(st+dr)/2;
      if(v[med]>=x){
        ans=med;
        dr=med-1;
      }else{
        st=med+1;
      }

    }
    return ans;
}

int main()
{
    int n, type, tests, x;
    fin>>n;
    for (int i = 0; i<n; i++){
        fin>>v[i];
    }
    fin>>tests;
    for(int i = 0; i < tests; i++){
        fin>>type;
        fin>>x;
        if(type == 0 || type == 1){
            fout<<cautbin1(0, n-1, x, type)+1<<'\n';
        }else
            fout<< cautbin2(0, n-1, x)+1<<'\n';
    }
    return 0;
}