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