#include <bits/stdc++.h>

using namespace std;
ifstream f("cautbin.in");
ofstream g("cautbin.out");
const int N=100010;
int n,a[N],m,c,x;
int cautare(int val)
{
    int st=1,dr=n,mi;
    while(st<=dr)
    {
        mi=(st+dr)/2;
        if(a[mi]==val)
            return mi;
        if(a[mi]>val)
            dr=mi-1;
        else
            st=mi+1;
    }
    return -1;
}
int pozitie1(int val)
{
    int st=1,dr=n+1,mi;
    while(dr-st>1)
    {
        mi=(st+dr)/2;
        if(a[mi]<=val)
            st=mi;
        else dr=mi;
    }
    return st;
}
int pozitie2(int val)
{
    int st=0,dr=n,mi;
    while(dr-st>1)
    {
        mi=(st+dr)/2;
        if(a[mi]<val)
            st=mi;
        else dr=mi;
    }
    return dr;
}
int main()
{
    f>>n;
    for(int i=1;i<=n;i++)
        f>>a[i];
    f>>m;
    for(int i=1;i<=m;i++)
    {
        f>>c>>x;
        if(c==0)
            g<<cautare(x)<<'\n';
        if(c==1)
            g<<pozitie1(x)<<'\n';
        if(c==2)
            g<<pozitie2(x)<<'\n';
    }
    return 0;
}