#include <bits/stdc++.h>
#include <string>
using namespace std;

ifstream fin ("cautbin.in");
ofstream fout ("cautbin.out");

int n;
long long int v[100002];
int cer;
int x,m;

int cauta(int x,int st,int dr)
{
    int m=(st+dr)/2;
    if(st<dr)
    {

        if(v[m]==x) return m;
        else if(v[m]<x) cauta(x,m+1,n);
            else cauta(x,1,m-1);
    }
    else return -m;
}



int main()
{
    fin>>n;
    for(int i=1;i<=n;i++) fin>>v[i];

    fin>>m;
    for(int i=1;i<=m;i++)
    {
        fin>>cer>>x;
        int pos=cauta(x,1,n);
        if(cer==0)
        {
            while(v[pos]==x) pos++;
            fout<<pos-1;
        }
        else if(cer==1)
        {
            while(v[pos]<=x) pos++;
            fout<<pos-1;
        }
        else
        {
            while(v[pos]>=x) pos--;
            fout<<pos+1;
        }
        fout<<'\n';
    }


    return 0;
}