#include <iostream>
#include <fstream>

using namespace std;

int v[100001], N, M, mij, x, nr;

int cautare0(int k)
{
     int inf=1; 
     int sup=N;
     while (inf<=sup)
        {mij=inf+(sup-inf)/2;
         if (v[mij]>k) 
             inf=mij-1;
         else 
             if (v[mij]<k)
                 inf=mij+1;
             else 
                 return mij;}
     return -1;
;                     
           
}

int cautare1 (int k)
{
    int p=0;
    int inf=1;
    int sup=N;
    while (inf<=sup)
       {mij=inf+(sup-inf)/2;
        if (v[mij]<=k)
           {inf=mij+1;
            p=mij;}
        else
            sup=mij-1;}
    return p;                                   
}

int cautare2 (int k)
{
    int p=0;
    int inf=1;
    int sup=N;
    while (inf<=sup)
       {mij=inf+(sup-inf)/2;
        if (v[mij]>=k)
           {sup=mij-1;
            p=mij;}
        else
            inf=mij+1;}
    return p;                                
}   

int main()
{
    ifstream f("cautbin.in");
    ofstream g("cautbin.out");
    f>>N;
    for (int i=1; i<=N; i++)
         f>>v[i];
    f>>M; 
    for (int j=0; j<M; j++)
       {f>>nr>>x;
        if (nr==0)        
              g<<cautare0(x);      
        if (nr==1)      
              g<<cautare1(x);
        if (nr==2)     
              g<<cautare2(x);}
    f.close();
    g.close();          
    return 0;         
}