#include<fstream>
#include<vector>
#include<algorithm>
using namespace std;
ifstream f("cautbin.in"); ofstream g("cautbin.out");

int n, m, t, x;
vector<int> a;
int main()
{
    f >> n;
    int el;
    for(int i = 1; i <= n; ++i) f >> el, a.push_back(el);
    f>>m;
    vector<int> :: iterator poz;
    while(m--)
    {
        f >> t >> x;
        if(!t)
        {
            poz = upper_bound(a.begin(), a.end(), x);
            if(poz != a.end())
                g<<(*poz) - 1<<'\n';
            else
                g<<-1<<'\n';
        }
        else
        if(t == 1)
        {
            poz = upper_bound(a.begin(), a.end(), x);
            if(poz != a.end())
                g<<(*poz) - 1<<'\n';
            else
            {
                while(poz == a.end())
                    poz = upper_bound(a.begin(), a.end(), --x);
                g<<(*poz) - 1<<'\n';
            }
        }
        else
        {
            poz =lower_bound(a.begin(), a.end(), x);
            if(poz != a.end()) g<<(*poz) - 1<<'\n';
            else
            {
                while(poz == a.end())
                    poz = lower_bound(a.begin(), a.end(), ++x);
                g<<(*poz) - 1<<'\n';
            }
        }
    }
}