#include <iostream>

using namespace std;
int v[100005];

int cautbin1(int st, int dr, int x, int type){

    int ans=-1;
    int med;
    while(st<=dr){

      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;
    int med;
    while(st<=dr){

      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;
    cin>>n;
    for (int i = 0; i<n; i++){
        cin>>v[i];
    }
    cin>>tests;
    for(int i = 0; i < tests; i++){
    cin>>type;
    cin>>x;
    if(type == 0 || type == 1){
        cout<<cautbin1(0, n-1, x, type)+1<<endl;
    }else cout<< cautbin2(0, n-1, x)+1<<endl;
    }
    return 0;
}