#include<fstream>
using namespace std;
int a[100008],i,n,j,m,x,y;
ifstream f("cautbin.in");
ofstream g("cautbin.out");

void citire_vect()
{
     f>>n;
     for(i=1;i<=n;i++)
     f>>a[i];
     f>>m;
     
}
int cazu_0(int x)
{
int li=1,ls=n,mij;

while(li!=ls)
{
             mij=(li+ls+1)/2;
             if(x>=a[mij])
             li=mij;
             else
             ls=mij-1;
             }
             if(x!=a[li])
             return -1;
    
             return li;

}

int cazu_1(int x)
{int li=1,ls=n,mij;

while(li!=ls)
{
             mij=(li+ls)/2;
             if(x<=a[mij])
             ls=mij;
             else
             li=mij+1;
             }
             if(a[li]>x)
             return li-1;

return li;
}

int cazu_2(int x)
{
    int li=1,ls=n,mij;

while(li!=ls)
{
             mij=(li+ls)/2;
             if(x<=a[mij])
             ls=mij;
             else
             li=mij+1;
}
             if(a[li]<x)
             return li+1;

return li;
}





void cazuri()
{
for(i=1;i<=m;i++)
{
                 f>>x>>y;
                 if(x==0)
                 g<<cazu_0(y);
                 else
                 if(x==1)
                 g<<cazu_1(y);
                 else
                 if(x==2)
                g<<cazu_2(y);
                g<<"\n";
}
f.close();
}
                 
     int main()
     {
         
        citire_vect();
        cazuri();
        
        g.close();     
        return 0;
        }