#include <iostream>
#include <fstream>
using namespace std;
const int NMAX=100000;
int v[NMAX+1],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(dr1-st1>1)
    {
        mij1=(st1+dr1)/2;
        if(v[mij1]<=x)
            st1=mij1;
        else
            dr1=mij1;
    }
        return st1;
}
int cb2(int x)
{
    int st2=0,dr2=n,mij2;
    while(dr2-st2>1)
    {
        mij2=(st2+dr2)/2;
        if(v[mij2]>=x)
            dr2=mij2;
        else
            st2=mij2;
    }
        return dr2;
}
int main()
{
    ifstream fin("cautbin.in");
    ofstream fout("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)<<"\n";
        if(y==1)
        cout<<cb1(x)<<"\n";
        if(y==2)
        cout<<cb2(x)<<"\n";
    }
    return 0;
}