#include <iostream>
#include <algorithm>
#include <fstream>
using namespace std;
ifstream fin("cautbin.in");
ofstream gout("cautbin.out");
int main()
{

    long long n,m,a,b,r,k=0;
    fin>>n;
    int v[n];
    for(int i=0; i<n; ++i) fin>>v[i];
    fin>>m;
    int f[m];
    for(int i=0; i<m; ++i){
        fin>>a>>b;
        if(a==0){
            r=upper_bound(v,n+v,b)-v;
            --r;
            if(r>=0 && v[r]==r){
                gout<<r+1<<"\n";
            }
            else gout<<-1<<"\n";
        }
        else if(a==1){
            r=upper_bound(v,v+n,b)-v;
            --r;
            gout<<r+1<<"\n";
        }
        else if(a==2){
            r=lower_bound(v,v+n,b)-v;
            if(v[r]==b) gout<<r+1<<"\n";
            else gout<<r+1+1<<"\n";
        }
    }



    return 0;
}