#include <iostream>
#include <fstream>
using namespace std;
ifstream fin("cautbin.in");
ofstream fout("cautbin.out");
int n,m,a[100002],x,y;
int cb0(int x, int st, int dr)
{
    while(st<=dr)
    {
        int m=(st+dr)/2;
        if(a[m]<=x)
            st=m+1;
        else
            dr=m-1;
    }
    m=(st+dr)/2;
    if(a[m]>x)
        m--;
    if(a[m]==x)
        return m;
    return -1;
}
int cb1(int x, int st, int dr)
{
    while(st<dr)
    {
        int m=(st+dr)/2;
        if(a[m]<=x)
            st=m+1;
        else
            dr=m;
    }
    m=(st+dr)/2;
    if(a[m]>x)
        m--;
    return m;
}
int cb2(int x, int st, int dr)
{
    while(st<dr)
    {
        int m=(st+dr)/2;
        if(a[m]<x)
            st=m+1;
        else
            dr=m;
    }
    m=(st+dr)/2;
    if(a[m]<x)
        m++;
    return m;
}
int main()
{
    fin>>n;
    for(int i=0; i<n; i++)
        fin>>a[i];
    fin>>m;
    for(int i=0; i<m; i++)
    {
        fin>>y>>x;
        if(i!=m-1)
          {
           if(y==0)
                fout<<cb0(x,0,n-1)+1<<endl;
            if(y==1)
                fout<<cb1(x,0,n-1)+1<<endl;
            if(y==2)
                fout<<cb2(x,0,n-1)+1<<endl;}
            else
            {
                if(y==0)
                fout<<cb0(x,0,n-1)+1;
            if(y==1)
                fout<<cb1(x,0,n-1)+1;
            if(y==2)
                fout<<cb2(x,0,n-1)+1;
            }
    }
    return 0;
}