#include <bits/stdc++.h>

using namespace std;
ifstream f("cautbin.in");
ofstream g("cautbin.out");

const int NMax = 100003;

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

int cautbin1(int lo,int hi,int x){
    int mid;
    while(lo <= hi){
        mid = (lo + hi) / 2;
        if(a[mid] == x && (a[mid + 1] != x || mid == n)){
            return mid;
        }else
        if(a[mid] <= x){
            lo = mid + 1;
        }else
        if(a[mid] > x){
            hi = mid - 1;
        }
    }
    if(a[mid] != x) return -1;
}
int cautbin2(int lo, int hi,int x){
    int mid;
    while(lo <= hi){
        mid = (lo + hi) / 2;
        if(a[mid] <= x && (a[mid + 1] > x || mid == n)){
            return mid;
        }else
        if(a[mid] <= x){
            lo = mid + 1;
        }else
        if(a[mid] > x){
            hi = mid - 1;
        }
    }
    return -1;
}
int cautbin3(int lo, int hi, int x){
    int mid;
    while(lo <= hi){
        mid = (lo + hi) / 2;
        if(a[mid] >= x && (a[mid - 1] < x || mid == 1)){
            return mid;
        }else
        if(a[mid] >= x){
            hi = mid - 1;
        }else
        if(a[mid] < x){
            lo = mid + 1;
        }
    }
    return -1;
}
int main()
{
    f >> n;
    for(int i = 1; i <= n; ++i){
        f >> a[i];
    }
    f >> t;
    for(int i = 1; i <= t; ++i){
        f >> q >> x;
        if(q == 0){
            g << cautbin1(1,n,x) << '\n';
        }else
        if(q == 1){
            g << cautbin2(1,n,x) << '\n';
        }else
        if(q == 2){
            g << cautbin3(1,n,x) << '\n';
        }
    }
    return 0;
}