#include <iostream>
#include <fstream>
using namespace std;
ifstream f("cautbin.in");
ofstream g("cautbin.out");

int M,N;
int V[100000];

int cbin0(int Left,int Right ,int val)
{
    int Mid;
    while(Left<=Right)
    {
        Mid=Left+(Right-Left)/2;
         if(V[Mid]<=val)
            Left=Mid+1;
         else Right=Mid-1;
    }
    Mid=Left+(Right-Left)/2;
    if(V[Mid]>val)Mid--;
    if(V[Mid]==val)
        return Mid;
    return -1;
}

int cbin1(int Left,int Right,int val)
{
    int Mid;
    while(Left<Right)
    {
        Mid=Left+(Right-Left)/2;
        if(V[Mid]<=val)
            Left=Mid+1;
        else Right=Mid;
    }
        Mid=Left+(Right-Left)/2;
        if(V[Mid]>val)
        --Mid;
        return Mid;
}

int cbin2(int Left,int Right,int val)
{
    int Mid;
    while(Left<Right)
    {
        Mid=Left+(Right-Left)/2;
        if(V[Mid]<val)
           Left=Mid+1;
        else Right=Mid;
    }
    Mid=Left+(Right-Left)/2;
    if(V[Mid]<val)
        ++Mid;
    return Mid;
}
int main()
{
   int i,tip,val;
   f>>N;
   for(i=1;i<=N;i++)
    f>>V[i];
   f>>M;
   while(M--)
   {
       f>>tip>>val;
       if(tip==0)
          g<<cbin0(1,N,val)<<'\n';
       if(tip==1)
          g<<cbin1(1,N,val)<<'\n';
       if(tip==2)
          g<<cbin2(1,N,val)<<'\n';
   }
   return 0;
}