#include <fstream>

using namespace std;
ifstream f("cautbin.in");
ofstream g("cautbin.out");
int a[100005],n,m,x,y;
int caut1(int lo,int hi,int q){
    int nr = q,mid;
    while(lo <= hi){
        mid = (lo + hi)/2;
        if(a[mid] == q && a[mid+1] != q){
            return mid;
        }else
        if(a[mid] <= q){
            lo = mid + 1;
        }else
        if(a[mid] > q){
            hi = mid - 1;
        }
    }
    return -1;
}
int caut2(int lo,int hi,int q){
    int nr = q,mid;
    while(lo <= hi){
        mid = (lo + hi)/2;
        if(a[mid] <= q && a[mid+1] > q){
            return mid;
        }else
        if(a[mid] <= q){
            lo = mid + 1;
        }else
        if(a[mid] > q){
            hi = mid - 1;
        }
    }
}
int caut3(int lo,int hi,int q){
    int nr = q,mid;
    while(lo <= hi){
        mid = (lo + hi)/2;
        if(a[mid] >= q && a[mid-1] < q){
            return mid;
        }else
        if(a[mid] < q){
            lo = mid + 1;
        }else
        if(a[mid] >= q){
            hi = mid - 1;
        }
    }
}
int main()
{
    f >> n;
    for(int i = 1; i <= n; i++){
        f >> a[i];
    }
    f >> m;
    a[n+1] = -1;
    for(int i = 1; i <= m; i++){
        f >> x >> y;
        if(x == 0){
            g << caut1(1,n,y) <<'\n';
        }else
        if(x == 1){
            g << caut2(1,n,y) <<'\n';
        }
        if(x == 2){
            g << caut3(1,n,y) <<'\n';
        }
    }
    return 0;
}