#include<fstream>
using namespace std;
#define NMax 100001
ifstream f("cautbin.in");
ofstream g("cautbin.out");
int n,v[NMax],m,y[NMax],b[NMax];
int binary_search(int val)
{
    int i, step;
    for (step = 1; step < n; step <<= 1);
    for (i = 0; step; step >>= 1)
        if (i + step < n && v[i + step] <= val)
           i += step;
    return i;
}
int binary_search1(int val)
{
    int i, step;
    for (step = 1; step < n; step <<= 1);
    for (i = 0; step; step >>= 1)
        if (i + step < n && v[i + step] <= val)
           i += step;
    for(int j=n-i+2;j<=n;j++)
        {
            if(v[j]=v[i]) i=j;
        }
    return i;
}
void solve()
{
    for(int i=1;i<=m;i++)
        {
            if(b[i]==2) g<<y[binary_search(y[i])+1]<<'/n';
            if(b[i]==1) g<<y[binary_search(y[i])-1]<<'/n';
            if(b[i]==0) if(binary_search(y[i])) g<<binary_search1(y[i])<<'/n';
                        else g<<"-1"<<'/n';
        }
}
int main()
{
    f>>n;
    for(int i=1;i<=n;i++)
    f>>v[i];
    f>>m;
    for(int j=1;j<=m;j++)
    {
        f>>b[j]>>y[j];
    }
    f.close();
    g.close();
    return 0;
}