#include <iostream>
#include <bitset>
#include <fstream>
using namespace std;

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

int intreb0(int a[], int n, int x, int lg)
{
    int poz;
    for(poz=0; lg!=0; lg>>=1)
        if(lg+poz<n && a[lg+poz]<=x)
            poz+=lg;
    if(a[poz]==x)
        return poz;
    return -1;
}

int intreb1(int a[], int n, int x, int lg)
{
    int poz;
    for(poz=0; lg!=0; lg>>=1)
        if(lg+poz<n && a[lg+poz]<=x)
            poz+=lg;
    return poz;
}

int intreb2(int a[], int n, int x, int lg)
{
    int poz;
    for(poz=n; lg!=0; lg>>=1)
        if(poz-lg>0 && a[poz-lg]>=x)
            poz-=lg;
    return poz;
}

void citire(int a[], int &n, int &m, int lg)
{
    fin >> n;
    for (int i=1; i<=n; i++)
        fin >> a[i];
    fin >> m;
    int it, x;
    for (int j=1; j<=m; j++)
    {
        fin >> it >> x;
        if(it==0)
        {
            fout << intreb0(a,n,x,lg) << endl;
        }
        if(it==1)
        {
            fout << intreb1(a,n,x,lg) << endl;
        }
        if(it==2)
        {
            fout << intreb2(a,n,x,lg) << endl;
        }

    }

}


int main()
{
    int lg=1, a[100000],n,m;
    for (lg; lg<=n; lg<<=1);
    citire(a,n,m,lg);
    return 0;
}