#include <fstream>
#include <algorithm>
using namespace std;
ifstream fin("cautbin.in");
ofstream fout("cautbin.out");
int v[100001],i,j,mij,*ld,ls,a,b,r;
int main()
{int m,n;
        fin>>n;
    for(i=1;i<=n;i++)
        fin>>v[i];fin>>m;
    for(i=1;i<=m;i++)
    {
        fin>>a>>b;
        if(a==0)
        {
            ld=0;
            ld=upper_bound(v+1,v+1+n,b);
            if(*ld)
                fout<<*ld-1;
            else
                fout<<-1;
        }
                if(a==1)
        {
            ld=0;
            ld=upper_bound(v+1,v+1+n,b+1);
            fout<<*ld-1;

        }
          if(a==2)
        {
            ld=0;
            ld=lower_bound(v+1,v+1,b);
            fout<<*ld+1;
        }
        fout<<'\n';
    }
    return 0;
}