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


int  v[Nmax];


int cautbin(int p, int u, int key) {
    int m;

    while (p <= u) {
        m = (p + u) / 2;
        if (v[m] <= key)
            p = m + 1;
        else
            u = m - 1;
    }
    m = (p + u) / 2;

    if (v[m] > key) m --;
    if (v[m] == key)
        return m;
    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 x, i, k, M, N;

    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", &k);
        scanf("%d", &x);
        if(k == 0)
            printf("%d\n", cautbin(1, N, x));
        if(k == 1)
            printf("%d\n", cautbin1(1, N, x));
        if(k == 2)
            printf("%d\n", cautbin2(1, N, x));
    }

    return 0;
}