#include <bits/stdc++.h>
int a[100005];
using namespace std;
ifstream f("cautbin.in");
ofstream g("cautbin.out");
int search0(int n,int m,int ok)
{int z;
    while(n<m)
    {
        z=n+((m-n)/2);
        if(a[z]<=ok)
            n=z+1;
        else
            m=z-1;
    }
    z=n+((m-n)/2);
   if(a[z]>ok)z--;
   if(a[z]==ok)
    return z;

return -1;
}
int search1(int n,int m,int ok)
{
    int z;
    while(n<m)
    {
        z=n+((m-n)/2);
        if(a[z]<=ok)
            n=z+1;
        else
            m=z-1;
    }
    z=n+((m-n)/2);
    if(a[z]>ok)
        z--;

return z;
}
int search2(int n,int m,int ok)
{
    int z;
    while(n<m)
    {
        z=n+((m-n)/2);
        if(a[z]<ok)
            n=z+1;
        else
            m=z-1;
    }
    z=n+((m-n)/2);
    if(a[z]<ok)
        z++;

return z;
}

int main()
{
int n,m,tip,val;
f>>n;
for(int i=1;i<=n;i++)
    f>>a[i];
f>>m;
while(m--)
{
    f>>tip;
    f>>val;
    if(tip==0)
        g<<search0(1,n,val)<<'\n';
    if(tip==1)
        g<<search1(1,n,val)<<'\n';
    if(tip==2)
       g<<search2(1,n,val)<<'\n';
}
    return 0;
    f.close();
    g.close();
}