#include <fstream>
using namespace std;
ifstream in ("cautbin.in");
ofstream out ("cautbin.out");
int v[100001];

int cautaredetip0 (int p, int u, int val)
{
    int mijloc;
    while(p<=u)
    {
        mijloc=(p+u)/2;
        if(v[mijloc]<=val)
        p=mijloc+1;
        else u=mijloc-1;
    }
    mijloc=(p+u)/2;
    if(v[mijloc]==val)
    return mijloc;
            else
    return-1;
}
int cautaredetip1 (int p, int u, int val)
{
    int mijloc;
    while(p<u)
    {
        mijloc=(p+u)/2;
        if(v[mijloc]<=val)
        p=mijloc+1;
        else u=mijloc;
    }
    mijloc=(p+u)/2;
    if(v[mijloc]>val)
    --mijloc;
    return mijloc;
}
int cautaredetip2 (int p, int u, int val)
{
    int mijloc;
    while(p<u)
        {
            mijloc=(p+u)/2;
            if(v[mijloc]<val)
            p=mijloc+1;
            else u=mijloc;
        }
    mijloc=(p+u)/2;
    if(v[mijloc]<val)
    mijloc++;
    return mijloc;
}
int main()
{

      int n, val, tip,m;
      in>>n;
      for(int i=1; i<=n; i++)
      in>>v[i];
      in>>m;
      while (m--)
      {
          in>>tip>>val;
          if(tip==0)
          out<<cautaredetip0(1,n,val)<<"\n";
          if(tip==1)
          out<<cautaredetip1(1,n,val)<<"\n";
          if(tip==2)
          out<<cautaredetip2(1,n,val)<<"\n";
      }
      return 0;
}