#include <bits/stdc++.h>

using namespace std;

#define N 100010

int v[N];

int CautBin0(int a,int b,int x)
{
    int m;
    while(a<=b)
    {
        m=(a+b)/2;
        if(v[m]<=x)
            a=m+1;
        else
            b=m-1;
    }
    m=(a+b)/2;
    if(v[m]>x)
        m--;
    if(v[m]==x)
        return m;
    return -1;
}

int CautBin1(int a,int b,int x)
{
    int m,n=b;
    while(a<b)
    {
        m=(a+b)/2;
        if(v[m]<=x)
            a=m+1;
        else
            b=m;
    }
    m=(a+b)/2;
    if(v[m]>x)
        m--;
    return m;
}

int CautBin2(int a,int b,int x)
{
    int m;
    while(a<b)
    {
        m=(a+b)/2;
        if(v[m]<x)
            a=m+1;
        else
            b=m;
    }
    m=(a+b)/2;
    if(v[m]<x)
        m++;
    return m;
}

int main()
{
    int n,m,x,alg;
    ifstream f("cautbin.in");
    ofstream g("cautbin.out");

    f>>n;
    for(int i=1;i<=n;i++)
        f>>v[i];
    f>>m;
    for(int j=1;j<=m;j++)
    {
        f>>alg>>x;
        if(alg==0)
            g<<CautBin0(1,n,x)<<"\n";
        if(alg==1)
            g<<CautBin1(1,n,x)<<"\n";
        if(alg==2)
            g<<CautBin2(1,n,x)<<"\n";
    }

    return 0;
}