#include <iostream>
#include <fstream>
#include <algorithm>

using namespace std;

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

int n,i,m,k,a,*t;

int x[100005];

int main()
{
    fin>>n;

    for(i=1;i<=n;i++)
    {
        fin>>x[i];
    }

    fin>>m;
    for(i=1;i<=m;i++)
    {
        fin>>k>>a;
        if(k==2)
        {
            t=lower_bound (x+1, x+n+1, a);
            fout<<*t-1<<"\n";
        }
        if(k==1)
        {
            t=upper_bound (x+1, x+n+1, a);
            fout<<*t-1<<"\n";
        }
        if(k==0)
        {
            if(binary_search (x+1, x+n+1, a))
               {
                    t=upper_bound (x+1, x+n+1, a);
                    fout<<*t-1<<"\n";
               }
            else fout<<-1;

        }
    }
}