#include <bits/stdc++.h>

using namespace std;
 ifstream fin("cautbin.in");
    ofstream fout("cautbin.out");
int a[100005], n;

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

}

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

}

int cautbin2(int x)
{

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

}

int main()
{
    int m,t,x,i;

    fin >> n;
    for(i = 1; i<=n; i++)
        fin >> a[i];
    fin >> m;
    while(m--)
    {
        fin >> t >> x;
        switch(t)
        {
        case 0:
            fout << cautbin0(x) << "\n";
            break;
        case 1:
            fout << cautbin1(x) << "\n";
            break;
        case 2:
            fout << cautbin2(x) << "\n";
            break;
        }
    }

    return 0;
}