//
//  main.cpp
//  cautbin
//
//  Created by Andrada Minca on 05.11.2024.
//

#include <fstream>
using namespace std;
ifstream fin ("cautbin.in");
ofstream fout ("cautbin.out");
int n,m,v[100005],c,q,i,t,s;
int main()
{
    fin>>n;
        for (i=1;i<=n;i++) fin>>v[i];
        fin>>m;
        while (m)
            {
                fin>>c>>q;
                if (c==0)
                    {
                        t=upper_bound(v+1,v+n+1,q)-v-1;
                        if(v[t]!=q) fout<<-1<<"\n";
                        else fout<<t<<"\n";
                    }
                if (c==1)
                    {
                        t=upper_bound(v+1,v+n+1,q)-v-1;
                        while (v[t]>q)
                             t--;
                        fout<<t<<"\n";
                    }
                if (c==2)
                    {
                        t=lower_bound(v+1,v+n+1,q)-v-1;
                        //cout<<t<<" ";
                        while (v[t]<q)
                             t++;
                        fout<<t<<"\n";
                    }
                m--;
            }
    return 0;
}