#include <iostream>
#include <fstream>
using namespace std;
ifstream f("cautbin.in");
ofstream g("cautbin.out");
int n,y,M,x,v[100000];
int caut0(int a, int stg, int dr)
{
    int m;
    while(stg<=dr)
    {
        m=stg+(dr-stg)/2;
        if(v[m]<=a)stg=m+1;
         else dr=m-1;
    }
    m=stg+(dr-stg)/2;
    if(v[m]>a)m--;
    if(v[m]==a)return m;
    return -1;
}
int caut1(int a, int stg, int dr)
{
    int m;
    while(stg<dr)
    {
        m=stg+(dr-stg)/2;
        if(v[m]<=a)stg=m+1;
         else dr=m;
    }
    m=stg+(dr-stg)/2;
    if(v[m]>a)m--;
    return m;
}
int caut2(int a, int stg, int dr)
{
    int m;
    while(stg<dr)
    {
        m=stg+(dr-stg)/2;
        if(v[m]<a)stg=m+1;
         else dr=m;
    }
    m=stg+(dr-stg)/2;
    if(v[m]<a)m++;
    return m;
}
int main()
{
  f>>n;
  for(int i=1;i<=n;i++)
     f>>v[i];
  f>>M;
  for(int i=1;i<=M;i++)
  {
      f>>y>>x;
      if(y==0)g<<caut0(x,1,n)<<"\n";
       else if(y==1)g<<caut1(x,1,n)<<"\n";
        else g<<caut2(x,1,n)<<"\n";
  }
}