#include <bits/stdc++.h>

using namespace std;

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

const int N=100005;
int v[N],n;

int cb1(int target)
{
    int st=1,dr=n;

    while(st<=dr)
    {
        int mid=st+(dr-st)/2;

        if(v[mid] == target) return mid;
        else if(v[mid] > target) dr=mid-1;
        else st=mid+1;
    }

    return -1;
}

int cb2(int target)
{
    int st=1,dr=n,mij;

    while(st<dr)
    {
        mij=st+(dr-st)/2;

        if(v[mij] <= target) st=mij+1;
        else dr=mij;
    }

    mij=(st+dr)/2;
    if(v[mij] > target) mij--;
    return mij;
}

int cb3(int target)
{
    int st=1,dr=n,mij;

    while(st<dr)
    {
        mij=st+(dr-st)/2;

        if(v[mij] < target) st=mij+1;
        else dr=mij;
    }
    mij=(st+dr)/2;
    if(v[mij] < target) mij++;
    return mij;
}

int main()
{
    in>>n;

    for(int i=1;i<=n;i++) in>>v[i];

    int m;
    in>>m;

    for(int i=1;i<=m;i++)
    {
        int cod,x;
        in>>cod>>x;

        switch(cod)
        {
        case 0:
            out<<cb1(x)<<'\n';
            break;
        case 1:
            out<<cb2(x)<<'\n';
            break;
        case 2:
            out<<cb3(x)<<'\n';
            break;
        }
    }

    return 0;
}