#include <iostream>
#include <cstdio>

int N,A[100005];

int binary_search0(int target)
  {
      int lo, hi, mid,retin=-1;
      lo = 1;
      hi = N;
      while (lo <= hi)
      {
          mid = lo + (hi-lo)/2;
          if (A[mid] <= target)
                {if (A[mid]==target) retin=mid;
                lo=mid+1;}
            else
                hi = mid-1;
      }
      return retin;
  }

int binary_search1(int target)
{
    int lo,hi,mid,retin=-1;
    lo=1;
    hi=N;
    while (lo<=hi)
        {
            mid=lo+(hi-lo)/2;
            if (A[mid]<=target)
                {
                    retin=mid;
                    lo=mid+1;
                }
                else hi=mid-1;
        }
    return retin;
}

int binary_search2(int target)
{
    int lo,hi,mid,retin=-1;
    lo=1;
    hi=N;
    while(lo<=hi)
        {
            mid=lo+(hi-lo)/2;
            if (A[mid]>=target)
                {
                    retin=mid;
                    hi=mid-1;
                }
            else lo=mid+1;
        }
    return  retin;
}

using namespace std;

int main()
{
    freopen ("cautbin.in","r",stdin);
    freopen ("cutbin.out","w",stdout);
    int i,x,y,M;
    scanf("%d",&N);
    for (i=1;i<=N;i++)
        scanf("%d",&A[i]);
    scanf("%d",&M);
    for (i=1;i<=M;i++)
        {
            scanf("%d %d",&x,&y);
            if (x==0)
                printf("%d\n",binary_search0(y));
            else if (x==1)
                printf ("%d\n",binary_search1(y));
                else if (x==2)
                    printf ("%d\n",binary_search2(y));
        }
    fclose(stdin);
    fclose(stdout);
    return 0;
}