#include <iostream>
#include <fstream>
using namespace std;
int x,n,caz,t,v[100001],i,nr;
int caut0(int x)
{
    int poz=-1,s=1,d=n;
    while(s<=d)
    {
        int  t=(s+d)/2;
        if(x==v[t])poz=t;
        if(x>=v[t])s=t+1;
        else d=t-1;
    }
    return poz;
}
int caut1(int x)
{
    int poz=-1,s=1,d=n;
    while(s<=d)
    {
        t=(s+d)/2;

        if(x>=v[t])
        {
            s=t+1;
            poz=t;

        }
        else d=t-1;
    }
    return poz;
}
int caut2(int x)
{
    int poz=1,s=1,d=n;
    while(s<=d)
    {
        t=(s+d)/2;

        if(x>v[t])   s=t+1;
        else
        {
            d=t-1;
            poz=t;
        }
    }
    return poz;

}



int main()
{
    ifstream f("cautbin.in");
    ofstream g("cautbin.out");
    f>>n;
    for(i=1; i<=n; i++)f>>v[i];
    f>>nr;
    for(i=1; i<=nr; i++)
    {
        f>>caz>>x;
        if(caz==0) g<<caut0(x)<<endl;
        if(caz==1) g<<caut1(x)<<endl;
        if(caz==2)g<<caut2(x)<<endl;
    }



}