#include <iostream>
#include <fstream>
#include <bitset>
#include <algorithm>

using namespace std;

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

int cautBin0(int a[], int n, int x){
    int st, dr, mij, poz = -1;
    st = 1;
    dr = n;
    while(st <= dr){
        mij = (st + dr)/2;
        if(a[mij] == x){
            poz = mij;
            st = mij + 1;
        }
        else if(a[mij] < x)
                st = mij + 1;
             else dr = mij - 1;
    }
    return poz;
}

int cautBin1(int a[], int n, int x){
    int st, dr, mij, poz = 0;
    st = 1;
    dr = n;
    while(st <= dr){
        mij = (st + dr)/2;
        if(a[mij] <= x){
            poz = mij;
            st = mij + 1;
        }
        else dr = mij - 1;
    }
    return poz;
}

int cautBin2(int a[], int n, int x){
    int st, dr, mij, poz = 0;
    st = 1;
    dr = n;
    while(st <= dr){
        mij = (st + dr)/2;
        if(a[mij] >= x){
            poz = mij;
            dr = mij - 1;
        }
        else st = mij + 1;
    }
    return poz;
}

const int N = 1e5 + 1;

int main(){
    int a[N], n, m, op, x, i;
    fin >> n;
    for (i = 1; i <= n; i++)
        fin >> a[i];
    fin >> m;
    for (i = 1; i <= m; i++){
        fin >> op >> x;
        if(op == 0)
            fout << cautBin0(a, n, x) << '\n';
        else if(op == 1)
                fout << cautBin1(a, n, x) << '\n';
        else if(op == 2)
                fout << cautBin2(a, n, x) << '\n';
    }
    return 0;
}