#include<fstream>
#include<algorithm>

using namespace std;

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

int v[100005],m,st,dr,ok,poz;

int main()
{
    int k,i,x,op,n;
    fin>>n;
    for(i=1;i<=n;i++)fin>>v[i];
    fin>>k;
    for(i=1;i<=k;i++)
    {
        fin>>op>>x;
        if(op==0)
        {
            poz=upper_bound(v+1,v+n+1,x)-v;
            if(v[poz-1]==x)fout<<poz-1<<'\n';
            else fout<<-1<<'\n';
        }
        else if(op==1)poz=upper_bound(v+1,v+n+1,x)-v,fout<<poz-1<<'\n';
        else poz=lower_bound(v+1,v+n+1,x)-v,fout<<poz<<'\n';
    }
    return 0;
}