#include <fstream>
#define nmax 100001

using namespace std;

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

int a[nmax],pas,n;

int caut0(int x)
{
    pas=1<<16;
    int r=0;
    while(pas!=0)
    {
        if(r+pas<=n && a[r+pas]<=x)
            r+=pas;
        pas/=2;
    }
    if(a[r]!=x)
        return -1;
    return r;
}

int caut1(int x)
{
    pas=1<<16;
    int r=0;
    while(pas!=0)
    {
        if(r+pas<=n && a[r+pas]<=x)
            r+=pas;
        pas/=2;
    }
    return r;
}

int caut2(int x)
{
    pas=1<<16;
    int r=0;
    while(pas!=0)
    {
        if(r+pas<=n && a[r+pas]<x)
            r+=pas;
        pas/=2;
    }
    return r+1;
}

int main()
{
    int i,m,x,y;
    fin>>n;
    for(i=1;i<=n;i++)
        fin>>a[i];
    fin>>m;
    for(i=1;i<=m;i++)
    {
        fin>>x>>y;
        if(x==0)
            fout<<caut0(y);
        else if(x==1)
            fout<<caut1(y);
        else
            fout<<caut2(y);
        fout<<'\n';
    }

    return 0;
}