#include <iostream>
#include <stdio.h>
#include <math.h>
#include <stack>
#include <cstdlib>
#include <vector>
#include <algorithm>
#include <string.h>

using namespace std;

void sol();

int main() {
#ifdef PADREATI
    freopen("in.txt", "r", stdin);
#else
    freopen("cautbin.in", "r", stdin);
    freopen("cautbin.out", "w", stdout);
#endif
    sol();
    return 0;
}

#define N 100000
int n, m;
int v[N];
int op, val;

int bs(int val) {
    int left = 0;
    int right = n;
    if(v[right]==val) return right;
    
    while(right-left>1) {
        int mid = left + (right-left)/2;
        if(v[mid]<=val) {
            left = mid;
        } else {
            right = mid;
        }
    }
    return left+1;
}

int bs2(int val) {
    int left = 0;
    int right = n;
    if (v[left] >= val) return left+1;

    while (right - left > 1) {
        int mid = left + (right - left) / 2;
        if (v[mid] >= val) {
            right = mid;
        } else {
            left = mid;
        }
    }
    return right + 1;
}

void sol() {
    scanf("%d", &n);
    for (int i = 0; i < n; i++) {
        scanf("%d", &v[i]);
    }
    scanf("%d", &m);
    while(m--) {
        scanf("%d %d", &op, &val);
        int pos = -1;
        switch(op) {
            case 0:
                pos = bs(val);
                printf("%d\n", (v[pos-1] == val) ? pos : -1);
                break;
            case 1:
                printf("%d\n", bs(val));
                break;
            default:
                printf("%d\n", bs2(val));
        }
    }
    
}