#include <iostream>
#include <fstream>
using namespace std;
int v[1000000],n;
int cb0(int x)
{
    int st=1,dr=n+1,mij;
    while(dr-st>1)
    {
        mij=(st+dr)/2;
        if(v[mij]<=x)
            st=mij;
        else
            dr=mij;
    }
    if(v[st]==x)
        return st;
    return -1;
}
int cb1(int x)
{
    int st1=1,dr1=n+1,mij1;
    while(dr-st>1)
    {
        mij=(st+dr)/2;
        if(v[mij]<=x)
            st=mij;
        else
            dr=mij;
    }
        return st;
}
int cb2(int x)
{
    int st2=0,dr2=n,mij2;
    while(dr-st>1)
    {
        mij=(st+dr)/2;
        if(v[mij]>=x)
            dr=mij;
        else
            st=mij;
    }
        return dr;
}
int main()
{
    ifstream cin ("cautbin.in");
    ofstream cout ("cautbin.out");
    int x,m,y;
    cin>>n;
    for(int i=1;i<=n;i++)
    {
        cin>>v[i];
    }
    cin>>m;
    for(int i=0;i<m;i++)
    {
        cin>>y>>x;
        if(y==0)
        cout<<cb0(x);
        if(y==1)
        cout<<cb1(x);
        if(y==2)
        cout<<cb2(x);
    }
    return 0;
}