#include <iostream>
#include <fstream>

using namespace std;

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

int n,v[100003],x,m;

int bs0(int st, int dr, int x) {
    int m;
    if(st>dr) return -1;
    else {
        m = st + (dr - st) / 2;
        if(v[m] < x) return bs0(m+1,dr,x);
        else  if(v[m] > x) return bs0(st, m-1,x);
            else
                {
                    if(m == dr) return m;
                    else
                        if(v[m+1] > x) return m;
                        else return bs0(m+1,dr,x);
                }
    }
}

int bs1(int st, int dr, int x){
    int m;
    m = st + (dr - st) / 2;
    if(v[m] > x) return bs1(st, m -1, x);
    else {
        if(m == dr) return m;
        else
            if(v[m+1] > x) return m;
            else return bs1(m+1,dr,x);
    }
}

int bs2(int st, int dr, int x){
    int m;
    m = st + (dr - st) / 2;
    if(v[m] < x) return bs2(m+1, dr, x);
    else {
        if(m == st) return m;
        else
            if(v[m-1] < x) return m;
            else return bs2(st, m-1,x);
    }
}

int main()
{
    int t,quest,val;
    f>>n;
    for(int i=1;i<=n;i++) f>>v[i];
    f>>t;
    while(t) {
            f>>quest>>val;
    if(quest == 0)
        g << bs0(1,n,val) << "\n";
    if(quest==1)
        g << bs1(1,n,val) << "\n";
    if(quest==2)
        g << bs2(1,n,val) << "\n";

    }
    return 0;
}