#include <bits/stdc++.h>
using namespace std;
 
const string file_name = "cautbin";
ifstream fin(file_name + ".in");
ofstream fout(file_name + ".out");
 
int main(){
 
    int n, m;
    vector<int> v;
    fin >> n;
 
    v.push_back(0);
    for (int i = 1; i <= n; i++){
        int x; fin >> x;
        v.push_back(x);
    }
    fin >> m;
    for(int i = 1; i <= m; i++){
        int c, x;
        fin >> c >> x;
        if(c == 0){
            int p = -1, st = 1, dr = n;
            while(st <= dr){
                int mid = (st + dr) / 2;
                if(v[mid] == x){
                    p = mid;
                    st = mid + 1;
                }
                else{
                    if(v[mid] > x)
                        dr = mid - 1;
                    else
                        st = mid + 1;
                }
            }
            fout << p << "\n";
        }
        else if(c == 1){
            int p = -1, st = 1, dr = n;
            while(st <= dr){
                int mid = (st + dr) / 2;
                if(v[mid] <= x){
                    p = mid;
                    st = mid + 1;
                }
                else
                    dr = mid - 1;
 
            }
            fout << p << "\n";
        }
        else{
            int p = -1, st = 1, dr = n;
            while(st <= dr){
                int mid = (st + dr) / 2;
                if(v[mid] >= x){
                    p = mid;
                    dr = mid - 1;
                }
                else
                    st = mid + 1;
            }
            fout << p << "\n";
        }
    }
 
 
 
    return 0;
}