#include <fstream>

using namespace std;
ifstream in("cautbin.in");
ofstream out("cautbin.out");
int v[100001];
int n;
int cautbin0(int val)
{
    int st=1,dr=n;
    while(dr-st>1)
    {
        int mijl=(st+dr)/2;
        if(v[mijl]>val)
            dr=mijl;
        else st=mijl;
    }
    if(val==v[st])
        return st;
    else return -1;
}
int cautbin1(int val)
{
    int st=1,dr=n;
    while(dr-st>1)
    {
        int mijl=(st+dr)/2;
        if(v[mijl]>val)
            dr=mijl;
        else st=mijl;
    }
    return st;
}
int cautbin2(int val)
{
    int st=1,dr=n;
    while(dr-st>1)
    {
        int mijl=(st+dr)/2;
        if(v[mijl]>=val)
            dr=mijl;
        else st=mijl;
    }
    if(v[st+1]==val)
    return st+1;
    else return st;
}
int main()
{
    int m;
    in>>n;
    for(int i=1;i<=n;i++)
        in>>v[i];
    in>>m;
    for(int i=1;i<=m;i++)
    {
        int p,j;
        in>>p>>j;
        if(p==0)
            out<<cautbin0(j)<<'\n';
        if(p==1)
            out<<cautbin1(j)<<'\n';
        if(p==2)
            out<<cautbin2(j)<<'\n';
    }
    return 0;
}