#include <iostream>
#include <cstring>
#include <fstream>
using namespace std;
ifstream fin("cautbin.in");
ofstream fout("cautbin.out");
int n,a[100001];
void citire()
{
    fin>>n;
    for(int i=0;i<n;i++)
    {
        fin>>a[i];
    }
}
void caut0(int val)
{
    int st=0,dr=n-1;
    int l=-2;
    while(st<=dr)
    {
        int mij=(st+dr)/2;
        if(a[mij]==val)
        {
            l=mij;
        }
        if(a[mij]<=val)
        {
            st=mij+1;
        }
        else
        {
            dr=mij-1;
        }
    }
    fout<<l+1<<'\n';
}
void caut1(int val)
{
    int st=0,dr=n-1;
    int l=-1;
    while(st<=dr)
    {
        int mij=(st+dr)/2;
        if(a[mij]<=val)
        {
            l=mij;
        }
        if(a[mij]<=val)
        {
            st=mij+1;
        }
        else
        {
            dr=mij-1;
        }
    }
    fout<<l+1<<'\n';
}
void caut2(int val)
{
    int st=0,dr=n-1;
    int l=-1;
    while(st<=dr)
    {
        int mij=(st+dr)/2;
        if(a[mij]>=val)
        {
            l=mij;
            dr=mij-1;
        }
        else
        {
            st=mij+1;
        }
    }
    fout<<l+1<<'\n';
}
void rezolvare()
{
    int m;
    fin>>m;
    for(int i=0;i<m;i++)
    {
        int c; fin>>c;
        int val; fin>>val;
        if(c==0)
        {
            caut0(val);
        }
        else
        {
            if(c==1)
            {
                caut1(val);
            }
            else
            {
                caut2(val);
            }
        }
    }
}
int main()
{
    citire();
    rezolvare();
    return 0;
}