#include <fstream>

using namespace std;
ifstream in("cautbin.in");
ofstream out("cautbin.out");
int v[100000], n;
int cautbin0(int x)
{
    int st=1, dr=n, mij, i;
    while(st<=dr)
    {
        mij=(st+dr)/2;
        if(v[mij]<=x)st=mij+1;
        else dr=mij-1;
    }
    if(v[i]==0)return -1;
    return dr;
}
int cautbin1(int x)
{
    int st=1, dr=n, mij;
     while(st<=dr)
    {
        mij=(st+dr)/2;
        if(v[mij]<=x)st=mij+1;
        else dr=mij-1;
    }
    return dr;
}
int cautbin2(int x)
{
    int st=1, dr=n, mij;
     while(st<=dr)
    {
        mij=(st+dr)/2;
        if(v[mij]>=x)st=mij+1;
        else dr=mij-1;
    }
    return st;
}
int main()
{

    int n, m, i, x, mij;
    in>>n;
    for(i=1;i<=n;i++)
        in>>v[i];
    in>>mij;
    for(i=1; i<=mij;i++)
    {
        in>>m>>x;
        if(m==0) out<< cautbin0(x)<<"\n";
        else if(m==1) out<<cautbin1(x)<<"\n";
        else out<<cautbin2(x)<<"\n";
    }
    return 0;
}