#include <iostream>
#include <fstream>

using namespace std;

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

const int Nmax = 100005;
int n, m, a[Nmax], sol;

void Caut0(int left, int right, int x)
{
    int mid;
    while(left < right)
    {
        mid = (left+right)/2;
        if(x < a[mid]) right = mid-1;
        else left = mid+1;
    }
    mid = (left+right)/2;
    if(a[mid] != x) mid--;
    if(a[mid] == x) sol = mid;
    else sol = -1;
}

void Caut1(int left, int right, int x)
{
    int mid;
    while(left < right)
    {
        mid = (left+right)/2;
        if(x < a[mid]) right = mid-1;
        else left = mid+1;
    }
    mid = (left+right)/2;
    if(a[mid] > x) mid--;
    sol = mid;
}

void Caut2(int left, int right, int x)
{
    int mid;
    while(left < right)
    {
        mid = (left+right)/2;
        if(x > a[mid]) left = mid+1;
        else right = mid-1;
    }
    mid = (left+right)/2;
    if(a[mid] < x) mid++;
    sol = mid;
}

int main()
{
    f>>n;
    for(int i = 1; i <= n; i++) f>>a[i];
    f>>m;
    while(m--)
    {
        int opt, x;
        f>>opt>>x;
        if(opt == 0) Caut0(1,n,x);
        if(opt == 1) Caut1(1,n,x);
        if(opt == 2) Caut2(1,n,x);
        g<<sol<<'\n';
    }
    return 0;
}