// Cautare binara

#include <fstream>
#define NMAX 100010
using namespace std;
int n,x[NMAX];
int caut0(int st, int dr, int key)
{
    int mij;
    while(st<=dr)
    {
     mij=(st+dr)/2;
     if(x[mij]<=key)
      st=mij+1;
     else
      dr=mij-1;
    }
    mij=(st+dr)/2;
    if(x[mij]>key) mij--;
    if(x[mij]==key)
     return mij;
    return -1;
}
int caut1(int st, int dr, int key)
{
    int mij;
    while(st<dr)
    {
     mij=(st+dr)/2;
     if(x[mij]<=key)
      st=mij+1;
     else
      dr=mij;
    }
    mij=(st+dr)/2;
    if(x[mij]>key) mij--;
    return mij;
}
int caut2(int st, int dr, int key)
{
    int mij;
    while(st<dr)
    {
     mij=(st+dr)/2;
     if(x[mij]<key)
      st=mij+1;
     else
      dr=mij;
    }
    mij=(st+dr)/2;
    if(x[mij]<key) mij++;
    return mij;
}
int main()
{
    int i,op,val,m;
    ifstream f("cautbin.in");
    ofstream g("cautbin.out");
    f>>n;
    for(i=1;i<=n;i++)
     f>>x[i];
    f>>m;
    for(i=1;i<=m;i++)
    {
     f>>op>>val;
     if(op==0) g<<caut0(1,n,val)<<"\n";
     else if(op==1) g<<caut1(1,n,val)<<"\n";
     else g<<caut2(1,n,val)<<"\n";
    }
    return 0;
}