#include <fstream>
#define NMAX 100001
using namespace std;
  ifstream f("cautbin.in");
    ofstream g("cautbin.out");
int x,n,caz,v[NMAX],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)
    {
     int   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)
    {
      int  t=(s+d)/2;

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

    }
    return poz;

}



int main()
{

    f>>n;
    for(i=1; i<=n; i++)f>>v[i];
    f>>nr;
while(nr--){

        f>>caz>>x;
        if(caz==0) g<<caut0(x)<<'\n';
        if(caz==1) g<<caut1(x)<<'\n';
        if(caz==2)g<<caut2(x)<<'\n';
}
return 0;


}