#include <iostream>
#include <fstream>
using namespace std;
ifstream fin("cautbin.in");
ofstream fout("cautbin.out");
int v[100010],N;
int binar0(int nr)
{
    int s,d,mij,ok=0,rez=-1;
    s=1;
    d=N;
    while(s<=d&&ok==0)
    {
        mij=(d-s)/2+s;
        if(v[mij]==nr&&v[mij+1]!=nr)
        {
            ok=1;
            rez=mij;
        }
        else
        {
            if((v[mij]==nr&&v[mij+1]==nr)||v[mij]<nr)
                s=mij+1;
            else
                d=mij-1;
        }
    }
    return rez;
}
int binar1(int nr)
{
    int s,d,mij,ok=0,rez=-1;
    s=1;
    d=N;
    while(s<=d&&ok==0)
    {
        mij=(d-s)/2+s;
        if(v[mij]<=nr&&v[mij+1]>nr)
        {
            ok=1;
            rez=mij;
        }
        else
        {
            if(v[mij]<=nr&&v[mij+1]<=nr)
                s=mij+1;
            else
                d=mij-1;
        }
    }
    if(rez==-1)
    rez=N;
    return rez;
}
int binar2(int nr)
{
    int s,d,mij,ok=0,rez=-1;
    s=1;
    d=N;
    while(s<=d&&ok==0)
    {
        mij=(d-s)/2+s;
        if(v[mij]>=nr&&v[mij-1]<nr)
        {
            ok=1;
            rez=mij;
        }
        else
        {
            if(v[mij]>=nr&&v[mij+1]>=nr)
                d=mij-1;
            else
                s=mij+1;
        }
    }
    if(rez==-1)
        rez=1;
    return rez;
}
int main()
{
    int M,i,nr,x;
    fin>>N;
    for(i=1; i<=N; i++)
    {
        fin>>v[i];
    }
    fin>>M;
    for(i=1; i<=M; i++)
    {
        fin>>x>>nr;
        if(x==0)
        {
            fout<<binar0(nr)<<'\n';
        }
        else
        {
            if(x==1)
            {
                fout<<binar1(nr)<<'\n';
            }
            else
            {
                fout<<binar2(nr)<<'\n';
            }
        }
    }
}