#include <stdlib.h>
#include <stdio.h>
#define Nmax 100010


int  v[Nmax];


int cautbin(int lo, int hi,  int x)
{
    int mid;
    while(lo <= hi)
    {
        mid = lo + (hi-lo)/2;
        if(v[mid] <= x)
            lo = mid + 1;
        else
            hi = mid - 1;
    }
    mid = lo + (hi-lo)/2;

    if(v[mid] > x)
        --mid;
    if(v[mid] == x)
        return mid;
    return -1;
}

int cautbin1(int lo, int hi,  int x)
{
   int mid;
   while(lo < hi)
   {
       mid = lo + (hi-lo)/2;
       if(v[mid] <= x)
            lo = mid + 1;
       else
            hi = mid;
   }

   mid = lo + (hi-lo)/2;
   if(v[mid] > x)
        --mid;
   return mid;
}

int cautbin2(int lo, int hi,  int x)
{
    int mid;

    while( lo < hi )
    {
        mid = lo + (hi-lo)/2;
        if(v[mid] < x)
            lo = mid + 1;
        else
            hi = mid;
    }

    mid = lo + (hi-lo)/2;
    if(v[mid] < x)
        ++mid;
    return mid;
}

int main () {
    int i, n, m, tip, val;

    freopen("cautbin.in","r",stdin);
    freopen("cautbin.out","w",stdout);
    scanf("%d", &n);
    for (i = 1; i <= n; ++ i)
        scanf("%d", &v[i]);

    scanf("%d", &m);

    while (m --){
          scanf("%d%d", &tip, &val);
          if (tip == 0)
             printf("%d\n", cautbin(1, n, val));
          if (tip == 1)
             printf("%d\n", cautbin1(1, n, val));
          if (tip == 2)
             printf("%d\n", cautbin2(1, n, val));
    }
    exit(0);
}