#include <bits/stdc++.h>
using namespace std;
ifstream f("cautbin.in");
ofstream g("cautbin.out");
int N,i,x,A[100005],M,nr;
int Intreb0(int N, int A[100005], int x)
{
    int i,poz,dr,st,m;
    poz=0; st=1; dr=N;
    m=(st+dr)/2;
    while(st<=dr){
        if(A[m]<=x){
            if(A[m]==x)poz=m;
            st=m+1;
        }
        else dr=m-1;
        m=(st+dr)/2;
    }
    if(poz==0)return -1;
    return poz;
}
int Intreb1(int N, int A[100005], int x)
{
    int i,poz,dr,st,m;
    poz=0; st=1; dr=N;
    m=(st+dr)/2;
    while(st<=dr){
        if(A[m]<=x){
            poz=m;
            st=m+1;
        }
        else dr=m-1;
        m=(st+dr)/2;
    }
    return poz;
}
int Intreb2(int N, int A[100005], int x)
{
    int i,poz,dr,st,m;
    poz=0; st=1; dr=N;
    m=(st+dr)/2;
    while(st<=dr){
        if(A[m]>=x){
            poz=m;
            dr=m-1;
        }
        else st=m+1;
        m=(st+dr)/2;
    }
    return poz;
}
int main()
{
    f>>N;
    for(i=1; i<=N; i++)f>>A[i];

    f>>M;
    for(i=1; i<=M; i++){
        f>>nr>>x;
        if(nr==0)g<<Intreb0(N,A,x)<<'\n';
        else if(nr==1)g<<Intreb1(N,A,x)<<'\n';
        else g<<Intreb2(N,A,x)<<'\n';
    }
    return 0;
}