#include <iostream>
#include <fstream>

using namespace std;

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

int c[100000];
int cautare_binara1(int a,int b[],int i)
{
    int p=0,st=0,dr=i+1,mid;
    while (dr-st>1)
    {
        mid=st+(dr-st)/2;
        if (b[mid]<a)
            st=mid;
        else
            dr=mid;
    }

    if (b[mid]==a)
    {
        while (b[mid]==b[mid+1])
            ++mid;
        return mid;
    }
    else
        return -1;
}
int cautare_binara2(int a,int b[],int i)
{
    int p=0,st=0,dr=i+1,mid;
    while (dr-st>1)
    {
        mid=st+(dr-st)/2;
        if (b[mid]<a)
            st=mid;
        else
            dr=mid;
    }

    if (b[mid]==a)
    {
        while (b[mid]==b[mid+1])
            ++mid;
        return mid;
    }
    else
    {
        return b[st];
    }
}
int cautare_binara3(int a,int b[],int i)
{
    int p=0,st=0,dr=i+1,mid;
    while (dr-st>1)
    {
        mid=st+(dr-st)/2;
        if (b[mid]<a)
            st=mid;
        else
            dr=mid;
    }

    if (b[mid]==a)
    {
        while (b[mid]==b[mid-1])
            --mid;
        return mid;
    }
    else
    {
        return b[dr];
    }
}
int main()
{
    int n,m,a,b,p;
    fin>>n;
    for (int i=1;i<=n;i++)
        fin>>c[i];
    fin>>m;
    for (int i=1;i<=m;i++)
    {
        fin>>a>>b;
        if (a==0)
            p=cautare_binara1(b,c,n);
        if (a==1)
            p=cautare_binara2(b,c,n);
        if (a==2)
            p=cautare_binara3(b,c,n);
        fout<<p<<'\n';
    }
    return 0;
}