#include <iostream>
#include <fstream>
using namespace std;
ifstream fin("cautbin.in");
ofstream fout("cautbin.out");
int n,v[100001];
int caut(int st,int dr,int y)
{
 int mij;
 while(st<=dr)
 {
     mij=(st+dr)/2;
     if(v[mij]<=y) st=mij+1;
     else dr=mij+1;
     mij=(st+dr)/2;
}
     while(v[mij]>y) mij--;
     if(v[mij]<y)  return -1;
     return mij;
}
int cautmin(int st,int dr,int y)
{
    int mij;
    while(st<dr)
    {
        mij=(st+dr)/2;
        if(v[mij]<=y) st=mij+1;
        else dr=mij;

    }
    mij=(st+dr)/2;
    while(v[mij]>y) mij--;
    return mij;
}
int cautmax(int st,int dr,int y)
{
    int mij;
    while(st<dr)
    {
        mij=(st+dr)/2;
        if(v[mij]>y) st=mij+1;
        else dr=mij+1;
    }
    mij=(st+dr)/2;
    while(v[mij]<y) mij++;
    return mij;
}
int main()
{
    fin>>n;
    for(int i=1;i<=n;i++)
        fin>>v[i];
    int o;
    fin>>o;
    for(int i=1;i<=o;i++)
    {
        int x,y;
        fin>>x>>y;
        if(x==0)
            fout<<caut(1,n,y)<<'\n';
        if(x==1)
            fout<<cautmax(1,n,y)<<'\n';
        if(x==2)
            fout<<cautmin(1,n,y)<<'\n';
    }
    return 0;
}