//#include <iostream>
#include <fstream>
using namespace std;
ifstream in("cautbin.in");
ofstream cout("cautbin.out");
int v[100001];

int bsearch0(int s, int d, int x) {
    int m;
    while(s<=d) {
        m = (s+d)/2;
        if(v[m]>x)
            d = m-1;
        else
            s = m+1;
    }
    m = (s+d)/2;
    if(v[m]>x) m--;
    if(v[m] == x)
        return m;
    else
        return -1;
}

int bsearch1(int s, int d, int x) {
    int m;
    while(s<d) {
        m = (s+d)/2;
        if(v[m] <= x)
            s = m+1;
        else
            d = m;
    }
    m = (s+d)/2;
    if(v[m]> x)
        m--;
    return m;
}

int bsearch2(int s, int d, int x) {
    int m;
    while(s<d) {
        m = (s+d)/2;
        if(v[m] >= x)
            d = m-1;
        else
            s = m+1;
    }
    m = (s+d)/2;
    if(v[m]< x)
        m++;
    return m;
}

int main()
{
    int n,i,x,s,m,d,tip;
    in>>n;
    for(i = 1; i <= n; i++)
            in>>v[i];
    in>>m;
    for( i = 1; i <= m ; i ++) {
        in>>tip>>x;
        if(tip == 0) {
            cout<<bsearch0(1,n,x)<<'\n';
        } else if(tip == 1) {
            cout<<bsearch1(1,n,x)<<'\n';
        } else if(tip == 2) {
            cout<<bsearch2(1,n,x)<<'\n';
        }
    }

    return 0;
}