#include <bits/stdc++.h>

using namespace std;

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

#define Nmax 100000

int n,m,v[Nmax],x,c;

int bin0(int lo, int hi, int val){

    int mid;
    while(lo <= hi){
    mid= lo + (lo-hi)/2;
    if(v[mid]<=val)
        lo=m+1;
    else
        hi=m-1;
    }
    mid= lo+ (lo-hi)/2;
    if(v[mid] > val)
        mid--;
    if(v[mid] == val)
        return mid;
    return -1;

}

int bin1(int lo, int hi, int val){

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


}

int bin2(int lo, int hi, int val){

    int mid;
    while(lo<hi){
        mid=lo+(lo-hi)/2;
        if(v[mid] < val)
            lo=mid+1;
        else
            hi=mid;
    }
    mid=lo + (lo-hi)/2;
    if(v[mid] < val)
        mid++;
    return mid;


}

int main()
{
    in>>n;
    for(int i=1;i<=n;i++){
        in>>v[i];
    }
    in>>m;
    while(m){
        in>>c>>x;
        if(c == 0){
            out<<bin0(1,n,x)<<'\n';
        }
        if(c == 1){
            out<<bin1(1,n,x)<<'\n';
        }
        if(c == 2){
            out<<bin2(1,n,x)<<'\n';
        }
        m--;
    }
    return 0;
}