#include <bits/stdc++.h>

using namespace std;

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

int n,i,v[100002],m,cer,x;

int cb(int x)
{
    int pw=1, pos=0;
    while(pw<=n)
        pw*=2;
    pw/=2;
    while(pw)
    {
        if(pos+pw<=n)
            if(v[pos+pw]<=x)
                pos+=pw;
        pw/=2;
    }
    return pos;

}

int intrebare0(int x)
{
    int poz=cb(x);
    if(v[poz]==x)
        return poz;
    else
        return-1;
}

int intrebare2(int x)
{
    int pw=1, pos=0;
    while(pw<=n)
        pw*=2;
    pw/=2;
    while(pw)
    {
        if(pos+pw<=n)
            if(v[pos+pw]<x)
                pos+=pw;
        pw/=2;
    }
    return pos+1;
}

int main()
{
    in>>n;
    for(i=1;i<=n;i++)
    {
        in>>v[i];
    }
    in>>m;
    for(i=1;i<=m;i++)
    {
        in>>cer>>x;
        if(cer==0)
            out<<intrebare0(x)<<'\n';
        else if(cer==1)
            out<<cb(x)<<'\n';
        else
            out<<intrebare2(x)<<'\n';
    }
    return 0;
}