//
//  main.cpp
//  CautareBinara
//
//  Created by Ioana Teoc on 9/21/12.
//  Copyright (c) 2012 Ioana Teoc. All rights reserved.
//

#include <iostream>
#include<stdio.h>

using namespace std;
#define maxn 100005

int n, V[maxn];

int search(int x){
    int i = 0, step;
    for(step = 1; step*2 < n; step *= 2);
    for(i = 0; step > 1 && step + i <= n; ){
        if(V[step + i] > x)
            step /= 2 ;
        if(V[step + i] == x){
            break;
        }
        if(V[step + i] < x){
            if(i + 2*step <= n)
                i += step;
            else
                i = n - step;
        }
    }
    return step + i;
}

int main()
{
    int m, op, x, pos;
    freopen("cautbin.in", "r", stdin);
    freopen("cautbin.out", "w", stdout);
    cin >> n;
    for(int i = 1; i <=n; i++){
        cin >> V[i];
    }
    cin >> m;
    for(int i=1; i<=m; i++){
        cin >> op;
        cin >> x;
        if(x > V[n]){
            if(op == 1)
                cout << n << endl;
            continue;
        }
        pos = search(x);
        if(op == 0){
            if(V[pos] != x){
                cout << -1 << endl;
                continue;
            }
            while(V[pos + 1] == x)
                pos ++;
            cout << pos << endl;
        }
        else if(op == 1){
            if(V[pos] < x){
                cout << pos << endl;
                continue;
            }
            if(V[pos] > x){
                cout << pos - 1 << endl;
                continue;
            }
            while(V[pos + 1] == x)
                pos ++;
            cout << pos << endl;
        }
        else if(op == 2){
            if(V[pos] < x){
                cout << pos + 1 << endl;
                continue;
            }
            if(V[pos] > x){
                cout << pos << endl;
                continue;
            }
            while(V[pos - 1] == x)
                pos--;
            cout << pos << endl;
        }
    }
    
}