#include <bits/stdc++.h>

using namespace std;

int bs1(int v[], int st, int dr, int x){
    int y = -1;
    while(st <= dr){
        int mid = st + (dr - st) / 2;
        if(v[mid] == x)
            y = mid;
        if(v[mid] >= x)
            st = mid + 1;
        else dr = mid - 1;  
    }
    return y;
}

int bs2(int v[], int st, int dr, int x){
    int y;
    while(st <= dr){
        int mid = st + (dr - st) / 2;
        if(v[mid] <= x)
            y = mid, st = mid + 1;
        else dr = mid - 1;  
    }
    return y;
}

int bs3(int v[], int st, int dr, int x){
    int y;
    while(st <= dr){
        int mid = st + (dr - st) / 2;
        if(v[mid] >= x)
            y = mid, dr = mid - 1;
        else st = mid + 1;  
    }
    return y;
}

int main(){
    ifstream fin("cautbin.in");
    ofstream fout("cautbin.out");
    
    int n, a[100001], q;
    
    fin >> n;
    for(int i = 1; i <= n; i++){
        fin >> a[i];
    }
    
    fin >> q;
    for(int i = 1; i <= q; i++){
        int nr, x;
        fin >> nr >> x;
        if(nr == 0) fout << bs1(a, 1, n, x) << endl;
        if(nr == 1) fout << bs2(a, 1, n, x) << endl;
        if(nr == 2) fout << bs3(a, 1, n, x) << endl;
    } 
}