#include <iostream>
#include <bitset>
#include <fstream>

using namespace std;

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

int intrebarea0 (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 intrebarea1 (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 intrebarea2 (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;
    if(a[poz]>=x)return poz;
}


int main()
{
    int lg=1, a[100000], n, m, x, t;
    fin>>n;
     for(lg; lg<=n; lg<<=1);
    for(int i=1; i<=n; i++)
        fin>>a[i];
    fin>>m;
    for(int i=1; i<=m; i++)
    {
        fin>>t>>x;
        if(t==0) fout<<intrebarea0(a, n, x, lg)<<endl;
        if(t==1)  fout<<intrebarea1 (a, n, x,lg)<<endl;
        if(t==2)  fout<<intrebarea2 (a, n, x, lg)<<endl;

    }


    return 0;
}