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


int i, j, k, M, N, mid, maxim, minim;
long long int x, v[Nmax];


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

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

int cautbin2(int lo, int hi, long long int x)
{
    if(lo > hi)
        return -1;
    else
    {
        mid = lo + (hi - lo)/2;
        if(x <= v[mid])
        {
            if(mid < minim)
                minim = mid;
        }
        else
            if(x < v[mid])
                cautbin2(lo, mid, x);
            else
                cautbin2(mid+1, hi, x);
    }
    return maxim;
}

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)
    {
        maxim = v[1];
        minim = v[N];
        cin >> k;
        cin >> x;
        if(k == 0)
            cout << cautbin(1, N, x) + 1 << '\n';
        else
            if(k == 1)
                cout << cautbin1(1, N, x) + 1 << '\n';
            else
                cout << cautbin2(1, N, x) + 1 << '\n';
    }

    return 0;
}