#include <bits/stdc++.h>
using namespace std;

int v[100010];
ifstream fin("cautbin.in");
ofstream fout("cautbin.out");
#define cin fin
#define cout fout
int main(){
    cin.tie(0)->sync_with_stdio(0);
    int n;
    cin >> n;
    for(int i= 1; i <= n; i++){
        cin >> v[i];
    }
    
    int m;
    cin >> m;
    while(m--){
        int t, x;
        cin >> t >> x;
        
        if(t == 2){
            
            int l = 1, r = n, pos = 1e9; 
            while(l <= r){
                int tm = (l + r)/2;
                if(v[tm] >= x){
                    r = tm - 1;
                    pos = min(pos, tm);
                }else{
                    l = tm + 1;
                    
                    // v[tm] < x (nu ar trebuii sa actualize pos) 
                    // v[tm] = x (ar .... pos )
                }
            }
            cout << pos << '\n';
        }else if(t == 1){
            int l = 1, r = n, pos = 0; 
            while(l <= r){
                int tm = (l + r)/2;
                if(v[tm] > x){
                    r = tm - 1;
                
                }else{
                    l = tm + 1;
                    
                    // v[tm] < x (nu ar trebuii sa actualize pos) 
                    // v[tm] = x (ar .... pos )
                    pos = max(pos, tm);
                }
            }
            cout << pos << '\n';
        }else{
            int l = 1, r = n, pos = 0; 
            while(l <= r){
                int tm = (l + r)/2;
                if(v[tm] > x){
                    r = tm - 1;
                
                }else{
                    l = tm + 1;
                    
                    // v[tm] < x (nu ar trebuii sa actualize pos) 
                    // v[tm] = x (ar .... pos )
                    pos = max(pos, tm);
                }
            }
            if(v[pos] == x){
                cout << pos << '\n';
            }else{
                cout << -1 << '\n';
            }
            //cout << pos << '\n';
        }
    }
    
}