#include <fstream>

using namespace std;
ifstream fin("cautbin.in");
ofstream fout("cautbin.out");
int a[100005],n,m;
void bs0(int s,int d,int x)
{ int m;
  while(s<d)
  { m=(s+d)/2;
      if(a[m]<=x) s=m+1;
      else d=m-1;
  }
    m=(s+d)/2;
    if(a[m]>x) m--;
    if(a[m]==x) fout<<m;
    else fout<<-1;
    fout<<"\n";
}
void bs1(int s,int d,int x)
{ int m;
    while(s<d)
    {m=(s+d)/2;
        if(a[m]<=x) s=m+1;
        else d=m-1;
    }
    m=(d+s)/2;
    if(a[m]>x)m--;
    fout<<m;
    fout<<"\n";
}
void bs2(int s,int d,int x)
{  int m;
    while(s<d)
    { m=(s+d)/2;
        if(a[m]< x) s=m+1;
        else d=m;
    }
    m=(s+d)/2;
    if(a[m]>x)
        m--;
    fout<<m<<"\n";
}

int main ()
{   int i,op,x;
    fin>>n;
    for(i=1;i<=n;++i) fin>>a[i];
    fin>>m;
    for(i=1;i<=m;++i)
    { fin>>op>>x;
        if(op==0)
            bs0(1,n,x);
            else
        if(op==1)
            bs1(1,n,x);
        else bs2(1,n,x);
    }
    return 0;
}