#include <bits/stdc++.h>
using namespace std; 
int v[100001];
int main() {
	// your code goes here
	ifstream fin("cautbin.in");
	ofstream fout("Cautbin.out");
	int nr;
	fin >> nr;
	for(int i = 0; i < nr; i++){
	    fin >> v[i];
	}
    
    int nrcer;
    cin >> nrcer;
    int p, numarul;
    for(int i = 0; i < nrcer; i++){
        fin >> p >> numarul;
        int rasp = 0;
        if( p == 0){
            int dr = nr - 1, st = 0;
            while(st <= dr){
                int mij = (st + dr) / 2;
                if(v[mij] < numarul){
                    dr = mij - 1;
                }
                if(v[mij] > numarul){
                    st = mij + 1;
                }
                if(v[mij] == numarul){
                    fout << dr << endl;
                    rasp = 1;
                    break;
                }
            }
            if(rasp == 0){
                fout << -1  << endl;
            }
        }
        else if(p == 1){
            int dr = nr - 1, st = 0;
            while(st < dr){
                int mij = (st + dr) / 2;
                if(v[mij] <= numarul){
                    st = mij + 1;
                }
                else{
                    dr = mij - 1;
                }
            }
            fout << st << endl;
        }
        else{
            int dr = nr - 1, st = 0; 
            while(st < dr){
                int mij = (st + dr) / 2;
                if(v[mij] >= numarul){
                    dr = mij - 1;
                }
                else{
                    st = mij + 1;
                }
            }
            fout << dr + 1 << endl;
        }
    }
}