#include <stdio.h>
#include <stdlib.h>
#define Max 100000


int n,m,a[Max];

int bs(long x)
{
int lo,hi,mid;
lo = 1; hi = n;
while(lo <= hi)
{
mid = lo +(hi - lo)/2;
if(x < a[mid])hi = mid-1;
else if(x > a[mid])lo = mid+1;
else return mid;
}
return -1;
}
int cautbin1(int x)
{
    int st,dr,mid;
    int pos,gasit = 0;
    if(x == a[n])return n;
    else
    {
        st = 1;
        dr = n;
        mid = st + (dr - st)/2;
        while(st <= dr)
        {
            if(x == a[mid])
            {
                pos = mid;
                gasit = 1;
                st = mid + 1;
                mid = st + (dr - st)/2;
            }
            else
            {
                if(x > a[mid])
                {
                    st = mid + 1;
                    mid = st + (dr-st)/2;
                }
                else if(x < a[mid])
                {
                    dr = mid - 1;
                    mid = st + (dr-st)/2;
                }
            }
        }
    }
    if(gasit == 1)
    return pos;
    else
    return -1;
}
int cautbin2(int x)
{
    int st,dr,mid,pos,gasit = 0;
    pos = 0;
    if(x >= a[n])return n;
    else
    {
     st = 1;
    dr = n;
    mid = st + (dr-st)/2;
        while(st <= dr)
        {
            if(a[mid] <= x)
            {
            pos = mid;
            st = mid + 1;
            mid = st + (dr - st)/2;
            gasit = 1;
            }
            else if(a[mid] > x)
            {
                dr = mid-1;
                mid = st + (dr - st)/2;

            }
        }
    }
    return pos;
}
int cautbin3(int x)
{
    int st,dr,mid,pos,gasit;
    if(x <= a[1])return 1;
    else
    {
        st = 1;
        dr = n;
        mid = st + (dr-st)/2;
        while(st <= dr)
        {
            if(a[mid] >= x)
            {
                pos = mid;
                 dr = mid - 1;
                mid = st + (dr-st)/2;
                gasit = 1;
            }
            else if(x > a[mid])
            {
                st = mid + 1;
                mid = st + (dr - st)/2;

            }
        }
    }
    if(gasit == 1)return pos;
    else return -1;
}

int main()
{
    freopen("cautbin.in","rt",stdin);
    freopen("cautbin.out","wt",stdout);

    int i,x,y;

    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",bs(y));
      else if(x == 1)
      printf("%d\n",cautbin2(y));
      else if(x == 2)
      printf("%d\n",cautbin3(y));

    }

    return 0;
}