#include <fstream>
using namespace std;
#define Nmax 100000

ifstream fin("cautbin.in");
ofstream fout("cautbin.out");

int n,v[Nmax],m;
int cautbinar(int l, int r,int a,int b)
{
    if(l<=r)
    {
      int mid= l + (r-l)/2; // in loc de (l + r) /2
      if(a==0)
      {
            if(v[mid]==b)
            {
                return mid;
            }
      }
      else if(a==2)
      {
          if(v[mid]>=b)
          {
              return mid;
          }
      }
      else
      {
          if(v[mid]<=b)
          {
              return mid;
          }
      }

            if(v[mid]<b)
            {
                return cautbinar(mid+1,n,a,b);
            }
            else
            {
                return cautbinar(1,mid-1,a,b);
            }

    }
    return -1;
}
int main()
{
    fin>>n;
    for(int i=1;i<=n;++i)
    {
        fin>>v[i];
    }
    fin>>m;
    for(int i=1;i<=m;++i)
    {
        int a,b;
        fin>>a>>b;
        if(a==0)
        {
           int bin = cautbinar(1,n,a,b);
           fout<<cautbinar(bin,n,a,b)<<'\n';
        }
        else if(a==1)
        {
            int bin=cautbinar(1,n,a,b);
            fout<<cautbinar(bin,n,a,b)<<'\n';
        }
        else
        {
            int bin=cautbinar(1,n,a,b);
            fout<<cautbinar(1,bin,a,b)<<'\n';
        }
    }
    return 0;
}