#include <bits/stdc++.h>

using namespace std;

ifstream fin("cautbin.in");
ofstream fout("cautbin.out");

int a[100005],n;

int cb0(int x)
{
    int st=1,dr=n;
    int mij,p=-1;
    while(st<=dr)
    {
        mij=(st+dr)/2;
        if(a[mij]<x)
            st=mij+1;
        if(a[mij]>x)
            dr=mij-1;
        if(a[mij]==x)
            p=mij,st=mij+1;
    }
    return p;
}
///cea mai mare pozitie p pe care se afla un element cu
///valoarea mai mica sau egala cu x in sir
int cb1(int x)
{
    int st=1,dr=n;
    int mij,p=-1;
    while(st<=dr)
    {
        mij=(st+dr)/2;
        if(a[mij]<=x)
            st=mij+1,p=mij;
        else dr=mij-1;
    }
    return p;
}
///cea mai mica pozitie pe care se afla un element cu valoarea
///mai mare sau egala cu x in sir. Se garanteaza ca cel mai mare numar din sir este mai mare sau egal decat x
int cb2(int x)
{
    int st=1,dr=n;
    int mij,p=-1;
    while(st<=dr)
    {
        mij=(st+dr)/2;
        if(a[mij]>=x)
            dr=mij-1,p=mij;
        else st=mij+1;
    }
    return p;
}

int main()
{
    int x,i,m,op;
    fin>>n;
    for(i=1;i<=n;i++) fin>>a[i];
    fin>>m;
    for(i=1;i<=m;i++)
    {
        fin>>op>>x;
        if(op==0) fout<<cb0(x)<<'\n';
        if(op==1) fout<<cb1(x)<<'\n';
        if(op==2) fout<<cb2(x)<<'\n';
    }
    fout.close();
    return 0;
}