#include <iostream>
#include <fstream>

int v[131072]={0};

using namespace std;

int cer0(int x,int n)
{
    int i,s=-1;
    for(i=n-1;n;n>>=1)
    {
        if(v[i]==x)
        {
            s=i;
            i+=n>>1;
            continue;
        }
        if(v[i]<x&&v[i])
        {
            i+=n>>1;
            continue;
        }
        i-=n>>1;
    }
    return s+1;
}
int cer1(int x, int n)
{
    int i,s;
    for(i=n-1;n;n>>=1)
    {
        if(v[i]<=x&&v[i])
        {
            s=i;
            i+=n>>1;
            continue;
        }
        i-=n>>1;
    }
    return s+1;
}
int cer2(int x, int n)
{
    int i,s;
    for(i=0;n;n>>=1)
    {
        if(v[i]>=x)
        {
            s=i;
            i-=n>>1;
            continue;
        }
        i+=n>>1;
    }
    return s+1;
}

int main()
{
    ifstream fin("cautbin.in");
    ofstream fout("cautbin.out");
    int n,logn,m,cer,x;
    fin>>n;
    for(x=0;x<n;x++)
        fin>>v[x];
    logn=1;
    while(logn<=n)
        logn<<=1;
    fin>>m;
    for(n=0;n<m;n++)
    {
        fin>>cer>>x;
        if(!cer)
            fout<<cer0(x,logn)<<endl;
        if(cer==1)
            fout<<cer1(x,logn)<<endl;
        if(cer==2)
            fout<<cer2(x,logn)<<endl;
    }
    return 0;
}