# include <fstream>
using namespace std;
int n, m, a[100005];
struct tip {
       int q, x;};
tip b[100005];
ifstream fin ("cautbin.in");
ofstream fout ("cautbin.out");
void citire ()
{
     int i;
     fin>>n;
     for (i=1;i<=n;i++)
         fin>>a[i];
     fin>>m;
     for (i=1;i<=m;i++)
         fin>>b[i].q>>b[i].x;
}
int caut0 (int x)
{
    int st=1, dr=n, mid;
    while (st<=dr)
    {
          mid=st+(dr-st)/2;
          if (a[mid]==x)
             return mid;
          else
              if (a[mid]>=x)
                 dr=mid-1;
              else
                  st=mid+1;
    }
    return -1;
}
int caut1 (int x)
{
    int st=1, dr=n, mid, w=0;
    while (st<=dr)
    {
          mid=st+(dr-st)/2;
          if (a[mid]<=x)
             w=mid, st=mid+1;
          else
              dr=mid-1;
    }
    return w;
}
int caut2 (int x)
{
    int st=1, dr=n, w=0, mid;
    while (st<=dr)
    {
          mid=st+(dr-st)/2;
          if (a[mid]>=x)
            { w=mid; dr=mid-1;}
          else
              st=mid+1;
    }
    return w;
}
void rez ()
{
    int i;
    citire ();
    for (i=1;i<=m;i++)
        if (b[i].q==0)
           fout<<caut0(b[i].x)<<endl;
        else
           if (b[i].q==1)
              fout<<caut1(b[i].x)<<endl;
           else
              fout<<caut2(b[i].x)<<endl;
}
int main ()
{
    rez ();
    return 0;
}