#include <iostream>
#include <fstream>
#define Nmax 100002
using namespace std;
ifstream fin("cautbin.in");
ofstream fout("cautbin.out");
unsigned int a[Nmax],n;
int rez0(int x)
{
    //0 x - cea mai mare pozitie pe care se afla un element cu valoarea x sau -1 daca aceasta valoare nu se gaseste in sir
    int ls=1,ld=n,mij;
    while(ls<ld)
    {
        mij=(ls+ld)/2+1;
        if(a[mij]<=x)ls=mij;
        else ld=mij-1;
    }
    if(a[ls]==x)return ls;
    return (-1);
}
int rez1(int x)
{
    //1 x - cea mai mare pozitie pe care se afla un element cu valoarea mai mica sau egala cu x in sir.
    int ls=1,ld=n,mij;
    while(ls<ld)
    {
        mij=(ls+ld)/2+1;
        if(a[mij]<=x)ls=mij;
        else ld=mij-1;
    }
    return ls;
}
int rez2(int x)
{
   // 2 x - cea mai mica pozitie pe care se afla un element cu valoarea mai mare sau egala cu x in sir.
   int ls=1,ld=n,mij;
    while(ls<ld)
    {
        mij=(ls+ld)/2;
        if(a[mij]>=x)ld=mij;
        else ls=mij+1;
    }
    return ls;
}
int main()
{
    int op,x,m;
    fin>>n;
    for(int i=1;i<=n;i++)fin>>a[i];
    fin>>m;
    for(int i=1;i<=m;i++)
    {
        fin>>op>>x;
        if(op==0)fout<<rez0(x);
        else if(op==1)fout<<rez1(x);
        else fout<<rez2(x);
        fout<<'\n';
    }
    return 0;
}