#include <iostream>
#include <fstream>
using namespace std;
ifstream f("cautbin.in");
ofstream g("cautbin.out");

int a[100010],c,n,m,x,i;

void cautbin0(int x)
{
int st=1, dr=n,mid;
while (st<=dr){
mid=(st+dr)/2;
if (a[mid]<=x) {st=mid+1;}
else{dr=mid-1;}
}
mid=(st+dr)/2;
if (a[mid]!=x) mid--;
if (a[mid]!=x) g<<-1;
else g<<mid<<"\n";
}


void cautbin1(int x)
{
int st=1, dr=n,mid;
while (st<=dr){
mid=(st+dr)/2;
if (a[mid]<=x) {st=mid+1;}
else{dr=mid-1;}
}
mid=(st+dr)/2;
if (a[mid]>x) mid--;
g<<mid<<"\n";
}


void cautbin2(int x)
{
int st=1, dr=n,mid;
while (st<=dr){
mid=(st+dr)/2;

if (a[mid]>=x) {dr=mid-1;}
else  {st=mid+1;}
}
mid=(st+dr)/2;
if (a[mid+1]>=x) mid++;
g<<mid<<"\n";
}



int main()
{
f>>n;
for (i=1;i<=n;i++)
    f>>a[i];
f>>m;
for (i=1;i<=m;i++)
{
    f>>c>>x;
    if (c==0) cautbin0(x);
    if (c==1) cautbin1(x);
    if (c==2) cautbin2(x);

}




    return 0;
}