#include <iostream>
#include <fstream>
using namespace std;
ifstream in("cautbin.in");
ofstream out("cautbin.out");
int cautare0(unsigned v[],unsigned val,int n)
{
    int st=0,dr=n-1,m,poz=-2;
    while(st<=dr) {
        m =(st+dr)/2;
        if(v[m]==val) {
            poz = m;
            st = m+1;
        }
        else if(val<v[m])
            dr = m-1;
        else
            st = m+1;
    }
    return poz+1;
}
int cautare1(unsigned v[],unsigned val,int n)
{
    int st=0,dr=n-1,m,poz;
    while(st<=dr) {
        m = (st + dr)/2;
        if(v[m]<=val) {
            poz = m;
            st = m+1;
        }
        else
            dr = m-1;
    }
    return poz+1;
}
int cautare2(unsigned v[],unsigned val,int n)
{
    int st=0,dr=n-1,m,poz;
    while(st<=dr) {
        m = (st + dr)/2;
        if(v[m]>=val){
            poz = m;
            dr = m-1;
        }
        else st = m+1;
    }
    return poz+1;
}
int main()
{
    int n,m;
    in>>n;
    unsigned v[n];
    for(int i=0;i<n;i++)
        in>>v[i];
    in>>m;
    for(int i=0;i<m;i++){
        int x;
        unsigned val;
        in>>x;
        in>>val;
        if(x==0)
            out<<cautare0(v,val,n)<<'\n';
        else if(x==1)
            out<<cautare1(v,val,n)<<'\n';
        else
            out<<cautare2(v,val,n)<<'\n';
    }
}