#include <iostream>
#include <fstream>
using namespace std;

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

int v[100001];

int bin0(int n, int val){
    int left = 1;
    int right = n;
    while(left<right){
        int middle = (left+right)/2;
        if(v[middle+1]<=val){
            left = middle+1;
        }
        else{
            right = middle;
        }
    }
    if(v[left]==val){
        return left;
    }
    else{
        return -1;
    }
}

int bin1(int n, int val){
    int left = 1;
    int right = n;
    while(left<right){
        int middle = (left+right)/2;
        if(v[middle+1]<=val){
            left = middle+1;
        }
        else{
            right = middle;
        }
    }
    return left;
}

int bin2(int n, int val){
///left - middle && middle+1 - right
    int left = 1;
    int right = n;
    while(left<right){
        int middle = (left+right)/2;
        if(v[middle]>=val){
            right = middle;
        }
        else{
            left = middle+1;
        }
    }
    return left;
}

int main() {
    int n, M, x, cer;
    f>>n;
    for (int i =1; i<=n; i++){
        f>>v[i];
    }
    f>>M;
    for(int i=1; i<=M; i++){
        f>>cer>>x;
        if(cer==0){
            g<<bin0(n, x);
        }
        if(cer==1){
            g<<bin1(n, x);
        }
        if(cer==2){
            g<<bin2(n, x);
        }
        g<<"\n";
    }

    return 0;
}