#include <iostream>
#include<bits/stdc++.h>
using namespace std;
int n,m,t,x;
vector<int> v;
int cautbin(int x)
{
    int st=0,dr=n-1,LastApp=-2;
    while(st<=dr)
        {
            int mij=(dr-st)/2+st;
            if(v[mij]<x) {st=mij+1;continue;}
            if(v[mij]>x) {dr=mij-1;continue;}
            LastApp=mij;
            st=mij+1;
        }
    return LastApp;
}
int limsup(int x)
{
    int st=0,dr=n-1,LastApp=-1;
    while(st<=dr)
        {
            int mij=(dr-st)/2+st;
            if(v[mij]<=x) {LastApp=mij;st=mij+1;continue;}
            if(v[mij]>x) {dr=mij-1;continue;}
        }
    return LastApp;
}

int liminf(int x)
{
    int st=0,dr=n-1,LastApp=-1;
    while(st<=dr)
        {
            int mij=(dr-st)/2+st;
            if(v[mij]<x) {st=mij+1;continue;}
            if(v[mij]>=x) {LastApp=mij;dr=mij-1;continue;}
        }
    return LastApp;
}
int main()
{
    ifstream f("cautbin.in");
    ofstream g("cautbin.out");
    f>>n;v.resize(n);int i;
    for(i=0;i<n;++i) f>>v[i];
    f>>m;
    for(i=0;i<m;++i)
        {
            f>>t>>x;
            if(t==0) {g<<cautbin(x)+1<<'\n';continue;}
            if(t==1) {g<<limsup(x)+1<<'\n';continue;}
            if(t==2) {g<<liminf(x)+1<<'\n';continue;}
        }
    return 0;
}