#include <iostream>
#include <fstream>
#define inFile "cautbin.in"
#define outFile "cautbin.out"

using namespace std;

int n, t, tip, nr, v[100001];

int mini(int a, int b, int c)
{
    a = min(a,b);
    return min(a,c);
}

int maxi(int a, int b, int c)
{
    a = max(a,b);
    return max(a,c);
}

int c_fix(int begg, int endd)
{
    if(begg == endd){
        if(nr == v[begg]) return begg;
        return -1;
    }
    int k = (begg + endd) / 2;
    if(v[k] > nr) return c_fix(begg,k-1);
    else if(v[k] < nr) return c_fix(k+1,endd);
    return max(k,c_fix(k+1,endd));
}

int c_less(int begg, int endd)
{
    if(begg == endd){
        if(nr >= v[begg]) return begg;
        return -1;
    }
    int k = (begg + endd) / 2;
    if(v[k] > nr) return c_less(begg,k-1);
    else if(v[k] < nr) return c_less(k+1,endd);
    return max(k,c_less(k+1,endd));
}

int c_big(int begg, int endd)
{
    if(begg == endd){
        if(nr <= v[begg]) return begg;
        return 10014124;
    }
    int k = (begg + endd) / 2;
    if(v[k] > nr) return c_big(begg,k-1);
    else if(v[k] < nr) return c_big(k+1,endd);
    return min(k,c_big(begg,k-1));
}



void solve()
{
    ifstream fin(inFile);
    ofstream fout(outFile);

    fin>>n;
    for(int i = 1; i <= n; ++i) fin>>v[i];
    fin>>t;
    for(int k = 1; k <= t; ++k){
        fin>>tip>>nr;
        switch(tip){
            case 0:fout<<c_fix(1,n)<<"\n"; break;
            case 1:fout<<c_less(1,n)<<"\n"; break;
            case 2:fout<<c_big(1,n)<<"\n"; break;
        }
    }
}

int main()
{
    solve();
}