#include <iostream>
#include<fstream>
#include<algorithm>
#include<vector>

using namespace std;

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

int n, v[100000];
int q1(int x)
{
    int dr = n-1;
    int st = 0;
    int poz = 0;
    while(st<=dr)
    {
        int m = (st+dr)/2;
        if(v[m] == x)
            return m+1;
        if(v[m] > x){
            dr = m - 1;
        }
        else{
            st = m+1;
        }
    }
    return -1;
}
int q2(int x)
{
int dr = n-1;
int st = 0;
int p = 0;
    while(st<=dr)
    {
        int m = (st+dr)/2;
        if(v[m] <= x){
            st = m+1;
            p = m;
            }
        else
            dr = m-1;
    }
    return p+1;
}
int q3(int x)
{
    int dr = n-1;
    int st = 0;
    int p;
    while(st<=dr)
    {
        int m = (st+dr)/2;
        if(x <= v[m]){
            dr = m-1;
            p=m;
        }
        else{
            //return st+1;
            st = m+1;
        }

    }
    return p+1;
}
int main()
{
    f >> n;
    for(int i = 0; i < n;++i)
        f >> v[i];
    int m;
    f >> m;
    for(int i = 0; i < m; ++i)
    {
        short q;
        int x;
        f >> q >> x;
        if(q == 0)
            fout << q1(x) << endl;
        else if(q == 1)
            fout << q2(x) << endl;
        else
            fout << q3(x) << endl;
    }
    return 0;
}