#include <bits/stdc++.h>
using namespace std;
int n, a[100001];
int cautbin0(int x)
{
    int dr=n,st=1,mij,poz=-1;
    while (st<=dr)
    {
        mij=(dr-st)/2+st;
        if (a[mij]==x)
        {
            poz=mij;
            st=mij+1;
        }
        else
        if (a[mij]<x)
        {
            st=mij+1;
        }
        else
        {
            dr=mij-1;
        }
    }
    return poz;
}

int cautbin1(int x)
{
    int dr=n,st=1,mij,poz=0;
    while (st<=dr)
    {
        mij=(dr-st)/2+st;
        if (a[mij]<=x)
        {
            poz=mij;
            st=mij+1;
        }
        else
        {
            dr=mij-1;
        }
    }
    return poz;
}

int cautbin2(int x)
{
    int dr=n,st=1,mij,poz=0;
    while (st<=dr)
    {
        mij=(dr-st)/2+st;
        if (a[mij]>=x)
        {
            poz=mij;
            dr=mij-1;
        }
        else
        {

            st=mij+1;

        }
    }
    return poz;
}

int main()
{
    ifstream in("cautbin.in");
    ofstream out("cautbin.out");
    in>>n;
    int i,c,x,m;
    for (i=1;i<=n;i++)
    {
        in>>a[i];
    }
    in>>m;
    for (i=1;i<=m;i++)
    {
        in>>c>>x;
        switch (c)
        {
        case 0:out<<cautbin0(x)<<"\n";break;
        case 1:out<<cautbin1(x)<<"\n";break;
        case 2:out<<cautbin2(x)<<"\n";break;
        }
    }
    out.close();
    in.close();
     return 0;
}