#include <fstream>

using namespace std;
ifstream fin("cautbin.in");
ofstream fout("cautbin.out");
int v[100001];
inline int caut1(int j,int n)
{
    int st=1,dr=n,mij;
    while(st<=dr)
    {
        mij=(st+dr)/2;
        if(v[mij]==j&&(v[mij+1]>j||mij==n)) return mij;
        if(v[mij]<=j) st=mij+1;
        if(v[mij]>j) dr=mij-1;
    }
    return -1;
}
inline int caut2(int j,int n)
{
    int st=1,dr=n,mij;
    while(st<=dr)
    {
        mij=(st+dr)/2;
        if(v[mij]<=j&&(v[mij+1]>j||mij==n)) return mij;
        if(v[mij]<=j) st=mij+1;
        if(v[mij]>j) dr=mij-1;
    }
}
inline int caut3(int j,int n)
{
    int st=1,dr=n,mij;
    while(st<=dr)
    {
        mij=(st+dr)/2;
        if(v[mij]>=j&&(v[mij-1]<j||mij==1)) return mij;
        if(v[mij]<j) st=mij+1;
        if(v[mij]>=j) dr=mij-1;
    }
}
int main()
{
    int n,i,j,m,k;
    fin>>n;
    for(i=1;i<=n;i++) fin>>v[i];
    fin>>m;
    for(i=1;i<=m;i++)
    {
        fin>>k>>j;
        k++;
        if(k==1) fout<<caut1(j,n)<<"\n";
        if(k==2) fout<<caut2(j,n)<<"\n";
        if(k==3) fout<<caut3(j,n)<<"\n";
    }
}