//
//  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");

long long n, m, t, val;
int v[100000];
void citire(int v[],int n)
{
		if(n>0)
	{
		citire(v,n-1);
		fin>>v[n];
		
	}



}
int divide0(int val){
    long long sol = -1;
    long long 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)
{
    long long sol = -1;
    long long 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)
{
    long long sol = -1;
    long long 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;
	citire(v, 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;
		
    }
}