#include <iostream>
#include <fstream>

using namespace std;

ifstream fin("cautbin.in");
ofstream fout("cautbin.out");
int v[100005];
int binsearch1(int st,int dr,int val)
{
    int ans=-1;
    while(st<=dr)
    {
        int med=(st+dr)/2;
        if(v[med]<=val)
        {
            st=med+1;
            ans=med;
        } else {
            dr=med-1;
        }
    }
    return ans;
}

int binsearch2(int st,int dr,int val)
{
    int ans=-1;
    while(st<=dr)
    {
        int med=(st+dr)/2;
        if(v[med]>=val)
        {
            dr=med-1;
            ans=med;
        } else {
            st=med+1;
        }
    }
    return ans;
}

int main()
{
    int n,m,x,bin;
    fin>>n;
    for(int i=1;i<=n;i++)
        fin>>v[i];
    fin>>m;
    for(int i=1;i<=m;i++){
        fin>>bin>>x;
        if(bin==0 || bin==1)
        {
            fout<<binsearch1(1,n,x)<<'\n';
        }else fout<<binsearch2(1,n,x)<<'\n';
    }

    return 0;
}