#include<fstream>
#include<algorithm>
#include<vector>
#define In "cautbin.in"
#define Out "cautbin.out"
using namespace std;
vector< int >v;
vector< int > :: iterator it;
int main()
{
    int i,n,m,x,poz,t;
    ifstream fin(In);
    ofstream fout(Out);
    fin>>n;
    v.resize(n+1);
    for(i=1;i<=n;i++)
        fin>>v[i];
    fin>>m;
    for(i=1;i<=m;i++)
    {
        fin>>t>>x;
        if(t==0)
        {
            it = upper_bound(v.begin()+1,v.end(),x);
            poz = it - v.begin()-1;
            if(v[poz]==x)
                fout<<poz<<"\n";
            else
                fout<<"-1 ";
        }
        else
            if(t==1)
            {
                it = upper_bound(v.begin()+1,v.end(),x);
                poz = it - v.begin()-1;
                fout<<poz<<"\n";
            }
            else
            {
                it = lower_bound(v.begin()+1,v.end(),x);
                poz = it - v.begin();
                fout<<poz<<"\n";
            }
    }
    return 0;
}