#include <iostream>
#include <stdio.h>
#define Nmax 100012
using namespace std;


int i, k, M, N, mid;
int x, v[Nmax];


int cautbin(int lo, int hi, long long int x)
{
    int mid;

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

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

int cautbin1(int lo, int hi, long long int x)
{
   int mid, n = hi;

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

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

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

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

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

int main()
{
    freopen("cautbin.in", "r", stdin);
    freopen("cautbin.out", "w", stdout);

    cin >> N;
    for(i = 1; i <= N; ++i)
        cin >> v[i];
    cin >> M;
    for(i = 1; i <= M; ++i)
    {
        cin >> k;
        cin >> x;
        if(k == 0)
            cout << cautbin(1, N, x)  << '\n';
        else
            if(k == 1)
                cout << cautbin1(1, N, x) << '\n';
            else
                cout << cautbin2(1, N, x)  << '\n';
    }

    return 0;
}