#include <iostream>
#include <fstream>
 
using namespace std;
 
ifstream fin("cautbin.in");
ofstream fout("cautbin.out");
 
int n,m,v[100005];
 
int divide0(int val){
    int left=1,right=n,sol=-1;
    while(left<=right){
        int mid=(left+right)/2;
        if(val>v[mid]){
            left=mid+1;
        }else if(val<v[mid]){
            right=mid-1;
        }else{
            sol=mid;
            left=mid+1;
        }
    }
    return sol;
}
 
int divide1(int val){
    int left=1,right=n,sol=-1;
    while(left<=right){
        int mid=(left+right)/2;
        if(v[mid]<=val){
            sol=mid;
            left=mid+1;
        }else{
            right=mid-1;
        }
        }
    return sol;
}
 
int divide2(int val){
    int left=1,right=n,sol=-1;
    while(left<=right){
        int mid=(left+right)/2;
        if(v[mid]>=val){
            sol=mid;
            right=mid-1;
        }else{
            left=mid+1;
        }
    }
    return sol;
}
 
 
 
int main()
{
    fin>>n;
    for(int i=1;i<=n;i++)
        fin>>v[i];
    fin>>m;
    while (m--) {
	int t, val;
        fin >> t >> val;
        if(t == 0)
            fout << divide0(val) << '\n';
	else if(t == 1)
            fout << divide1(val) << '\n';
	else
            fout << divide2(val) << '\n';
    }
    return 0;
}