#include <fstream>
using namespace std;
ifstream f("cautbin.in");
ofstream g("cautbin.out");
int A[100000];
int caut1(int x,int p,int u)
{
    int m;
    while(p<=u)
    {
        m=p+(u-p)/2;
        if(A[m]<=x)
            p=m+1;
        else u=m-1;
    }
    m=(u+p)/2;
    if(A[m]>x)m--;
    if(A[m]==x) return m+1;
    return -1;
}
int caut2(int x,int p,int u)
{
    int m;
    while(p<u)
    {
        m=p+(u-p)/2;
        if(A[m]<=x) p=m+1;
        else u=m-1;
    }
    m=(u+p)/2;
    if(A[m]>x)m--;
    if(A[m]<=x) return m+1;
}
int caut3(int x,int p,int u)
{
    int m;
    while(p<u)
    {
        m=p+(u-p)/2;
        if(A[m]<x) p=m+1;
        else u=m;
    }
    m=p+(u-p)/2;
    if(A[m]<x) ++m;
    return m+1;
}
int main()
{int N,i,nr,x,M;
f>>N;
for(i=0;i<N;i++)
{
    f>>A[i];
}
f>>M;
for(i=0;i<M;i++)
{
    f>>nr>>x;
    if(nr==0)
        g<<caut1(x,0,N-1)<<'\n';
    else if(nr==1)
        g<<caut2(x,0,N-1)<<'\n';
    else g<<caut3(x,0,N-1)<<'\n';
}
}