#include <iostream>
#include <fstream>

using namespace std;

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

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

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

int cautare2 (int k, int inf, int sup)
{
    int p;
    while (inf<=sup)
       {mij=inf+(sup-inf)/2;
        if (v[mij]>=k)
           {p=mij;
            sup=mij-1;}
        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,1,N);      
        if (nr==1)      
              g<<cautare1(x,1,N);
        if (nr==2)     
              g<<cautare2(x,1,N);}
    f.close();
    g.close();          
    return 0;         
}