//#include <iostream>
#include <fstream>
#include <vector>
#include <algorithm>

using namespace std;
ifstream cin ("cautbin.in");
ofstream cout ("cautbin.out");

vector <int> x;
long long n,m,a,b,i,u;
int main()
{
    cin>>n;
    x.resize(n+1);
    for (i=1;i<=n;++i) cin>>x[i];

    cin>>m;
    for (i=1;i<=m;++i)
    {
        cin>>a>>b;
        u=0;
        if (a==0)
        {
            if (binary_search(x.begin(),x.end(),b))
            {
                u=*upper_bound(x.begin(),x.end(),b);
                cout<<u-1<<"\n";
            }
            else cout<<"-1"<<"\n";
        }
       else  if (a==1)
        {
            u=*upper_bound(x.begin(),x.end(),b);
            cout<<u-1<<"\n";
        }
        else if (a==2)
        {
            u=*lower_bound(x.begin(),x.end(),b);
            cout<<u-1<<"\n";
        }

    }
    return 0;
}