#include <bits/stdc++.h>

using namespace std;

int n,M;
int A[100005];

int bin(int x){
int st = 1, dr = n;
int r = -1;
while (st <= dr){
    int mid = (st+dr) / 2;
    if(A[mid] == x){
        r = mid;
        st = mid + 1;
    }
    else
    if(A[mid] < x)
        st = mid + 1;
    else dr = mid - 1;
}
return r;
}

int bin2(int x){
int st = 1, dr = n;
int r = -1;
while (st <= dr){
    int mid = (st+dr) / 2;
    if(A[mid] <= x){
        r = mid;
        st = mid + 1;
    }
    else dr = mid - 1;
}
return r;
}

int bin3(int x){
int st = 1, dr = n;
int r = -1;
while (st <= dr){
    int mid = (st+dr) / 2;
    if(A[mid] >= x){
        r = mid;
        dr = mid - 1;
    }
    else st = mid + 1;
}
return r;
}


int main()
{
    freopen("cautbin.in" , "r" , stdin);
    freopen("cautbin.out" , "w" ,stdout);
    cin.tie(0)->sync_with_stdio(0);
    cin >> n;
    for(int i = 1;i <= n; ++i)cin >> A[i];
    cin >> M;
    while (M--){
        int tip,x;
        cin >> tip >> x;
        if(tip == 0)
            cout << bin(x) << "\n";
        else
        if(tip == 1)
            cout << bin2(x) << "\n";
        else
            cout << bin3(x) << "\n";
    }
}