#include <iostream>
#include <fstream>
using namespace std;
int v[100000];
tip0(int st,int dr,int x){
    int m;
    while(st<=dr){
        m=(st+dr)/2;
        if(x>=v[m])
            st=m+1;
        else
            dr=m-1;
    }
    m=(st+dr)/2;
    if(v[m]>x) --m;
    if(v[m]==x) 
        return m;
    return -1;
}
tip1(int st,int dr,int x){
   int m;	
   while(st<dr){
        m=(st+dr)/2;
        if(x>=v[m])
            st=m+1;
        else
            dr=m;
    }
    m=(st+dr)/2;
    if(v[m]>x)
        --m;
    return m;
}
tip2(int st,int dr,int x){
	int m;
    while(st<=dr){
        m=(st+dr)/2;
        if(x>v[m])
            st=m+1;
        else
            dr=m;
    }
    m=(st+dr)/2;
    if(v[m]<x)
        ++m;
    return m;
}
int main(){
	freopen("cautbin.in", "r", stdin);
    freopen("cautbin.out", "w", stdout);
    int n,m2,st=1,dr,t,x,m=0;
    cin>>n;
    dr=n;
    for(int i=1; i<=n; ++i) cin>>v[i];
    cin>>m2;
    for(int i=1; i<=m2; ++i){
        cin>>t>>x;
        if(t==0)
            cout<<tip0(1,n,x);
        else if(t==1)
            cout<<tip1(1,n,x);
        else
            cout<<tip2(1,n,x);
    }
    return 0;
}