//
//  main.cpp
//  cautare_binara
//
//  Created by Daniel Marcu on 04/04/2019.
//  Copyright © 2019 Daniel Marcu. All rights reserved.
//

#include <iostream>
#include <fstream>

using namespace std;

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

int n, m, t, val;
int v[100000];

int divide0(int val){
    int sol = -1;
    int st = 1, dr = n;
    while(st <= dr){
        int m = (st + dr) / 2;
        if(v[m] == val){
            sol = m;
            st = m + 1;
        }else if(v[m] < val){
            st = m + 1;
        }else{
            dr = m - 1;
        }
    }
    return sol;
}

int divide1(int val)
{
    int sol = -1;
    int st = 1, dr = n;
    while(st <= dr){
        int m = (st + dr) / 2;
        if(v[m] <= val){
            st = m + 1;
	    sol = m;
        }else{
            dr = m - 1;
        }
    }
    return sol;
}

int divide2(int val)
{
    int sol = -1;
    int st = 1, dr = n;
    while(st <= dr){
        int m = (st + dr) / 2;
        if(v[m] < val){
            st = m + 1;
        }else{
	    sol = m;
            dr = m - 1;
        }
    }
    return sol;
}


int main()
{
    fin >> n;
    for(int i = 1; i <= n; i++)
        fin >> v[i];
    fin >> m;
    while (m--) {
        fin >> t >> val;
        if(t == 0)
            fout << divide0(val) << endl;
	else if(t == 1)
            fout << divide1(val) << endl;
	else
            fout << divide2(val) << endl;
		
    }
}