#include "bits/stdc++.h"

using namespace std;

const int NMax = 100003;

int a[NMax];
int n,m,q,x;

int main(){
    ifstream cin("cautbin.in");
    ofstream cout("cautbin.out");

    cin >> n;
    for(int i = 1; i <= n; ++i){
        cin >> a[i];
    }
    cin >> m;
    for(int i = 1; i <= m; ++i){
        cin >> q >> x;
        int lo = 1, hi = n;
        int mid = 0;
        
        if(q == 0){
            
            while(lo <= hi){
                mid = (lo + hi) / 2;
                if(a[mid] == x && (mid + 1 > n || a[mid + 1] > x)){
                    break;
                }else if(a[mid] <= x){
                    lo = mid + 1;
                }else {
                    hi = mid - 1;
                }
            }
            if(a[mid] == x){
                cout << mid << '\n';
            }else{
                cout << -1 << '\n';
            }

        } else if(q == 1){
            while(lo <= hi){
                mid = (lo + hi) / 2;
                if(a[mid] <= x && (mid + 1 > n || a[mid + 1] > x)){
                    break;
                }else if(a[mid] <= x){
                    lo = mid + 1;
                }else {
                    hi = mid - 1;
                }
            }
            //if(a[mid] == x){
                cout << mid << '\n';
            //}
        }else {
            while(lo <= hi){
                mid = (lo + hi) / 2;
                if(a[mid] >= x && (mid - 1 == 0 || a[mid - 1] < x )){
                    break;
                }else if(a[mid] >= x){
                    hi = mid - 1;
                }else {
                    lo = mid + 1;
                }
            }
            //if(a[mid] == x){
                cout << mid << '\n';
            //}
        } 
    }
    return 0;
}