#include <iostream>
#include <fstream>
#define MAX 100002
using namespace std;
int n,m,t,x,v[MAX];

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

int bin1(int x){
    /// cea mai din dreapta pozitie pe care se alfa un element cu valoarea x
    /// (sau -1)
    /// 0 0 0 0 0 1 1 1 0 0 0
    ///               ^
    /// 1 - (v[i] == x), 0 - altfel
    /// daca ne aflam pe 1 vrem sa ne ducem pe negru din fata
    /// daca ne aflam pe negru vrem sa ne ducem pe alb din spate
    int st = 1, dr = n, poz = -1;
    while(st <= dr){
        int mid = (st+dr)/2;
        if(v[mid] >= x){
            if(v[mid] == x){
                poz = mid;
            }
            st = mid+1;
        }else{
            dr = mid-1;
        }
    }
    return poz;
}

int bin2(int x){
    /// cea mai din dreapta pozitie cu v[poz] <= x
    /// 1 1 1 1 1 0 0 0 0 0 0
    ///         ^
    int st = 1, dr = n, poz = 0;
    while(st <= dr){
        int mid = (st+dr)/2;
        if(v[mid] <= x){
            st = mid+1;
            poz = mid;
        }else{
            dr = mid-1;
        }
    }
    return poz;
}

int bin3(int x){
    /// cea mai din stanga pozitie pe care v[poz] >= x
    /// 0 0 0 1 1 1 1 1 1
    ///       ^
    int st = 1, dr = n, poz = 0;
    while(st <= dr){
        int mid = (st+dr)/2;
        if(v[mid] >= x){
            dr = mid-1;
            poz = mid;
        }else{
            st = mid+1;
        }
    }
    return poz;
}

int main()
{
    fin >> n;
    for(int i = 1; i <= n; i++){
        fin >> v[i];
    }
    fin >> m;
    for(int i = 1; i <= m; i++){
        fin >> t >> x;
        if(t == 0){
            fout << bin1(x) << "\n";
        }else if(t == 1){
            fout << bin2(x) << "\n";
        }else if(t == 2){
            fout << bin3(x) << "\n";
        }
    }
    return 0;
}