#include <fstream>

using namespace std;

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

int m,c,x,n,i,y=2;
int v[100010];

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

    g << "\n";
}

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

    m = (s+d)/2;

    if(v[m]>x) m--;
    if(v[m]<=x) g << m;

    g << "\n";

}

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

    m = (s+d)/2;

    if(v[m]<x) m++;
    if(v[m]>=x) g << m;

    g << "\n";

}

int main()
{
    f >> n;
    for(i=1;i<=n;i++)
         f >> v[i];

    f >> m;

    for(i=0;i<m;i++){
        f >> c >> x;
        if(c==0) cbin(1,n);
        else if(c==1) cbinm(1,n);
            else cbinM(1,n);
        }

    return 0;
}