#include <iostream>
#include <fstream>
#include <vector>
using namespace std;

ifstream fin("cautbin.in");
ofstream fout("cautbin.out");

int n;
vector<int> sir;

void Read();

int BinarySearch_1(int x);
int BinarySearch_2(int x);
int BinarySearch_3(int x);

int main()
{
    Read();

    int qnums;
    fin >> qnums;

    int x, y;
    while ( qnums-- )
    {
        fin >> x >> y;

        if ( x == 0 )
            fout << BinarySearch_1(y) << '\n';
        if ( x == 1 )
            fout << BinarySearch_2(y) << '\n';
        if ( x == 2 )
            fout << BinarySearch_3(y) << '\n';
    }


    fin.close();
    fout.close();
    return 0;
}

int BinarySearch_3(int x)
{
    int st = 0, dr = n-1;
    int mid, rval = 0;

    while ( st <= dr )
    {
        mid = ( st + dr ) / 2;

        rval = sir[mid];
        dr = mid - 1;
    }

    return rval + 1;
}

int BinarySearch_2(int x)
{
    int st = 0, dr = n-1;
    int mid, rval = 0;

    while ( st <= dr )
    {
        mid = ( st + dr ) / 2;
        if ( sir[mid] <= x )
            rval = max ( rval, sir[mid] );

        if ( x <= sir[mid] )
            dr = mid - 1;
        else
        if ( x > sir[mid] )
            st = mid + 1;
    }

    return rval + 1;
}

int BinarySearch_1(int x)
{
    int st = 0, dr = n-1;
    int mid; int rval = -1;

    while ( st <= dr )
    {
        mid = ( st + dr ) / 2;
        if ( sir[mid] == x )
            rval = max ( rval, sir[mid] );

        if ( x >= sir[mid] )
            st = mid + 1;
        else
        if ( x < sir[mid] )
            dr = mid - 1;
    }
    if ( rval != -1 ) return rval + 1;
    return rval;
}

void Read()
{
    fin >> n; int x;
    for (int i = 0; i < n; ++i)
    {
        fin >> x;
        sir.push_back(x);
    }
}