#include <iostream>
#include <fstream>
using namespace std;
ifstream f("cautbin.in");
ofstream g("cautbin.out");
int a[100005],n,m;
int Cbin(int x)
{ int l=1,r=n,mid;
while(l<r)
{ mid=(l+r)/2;
if (x>=a[mid]) l=mid+1; else r=mid-1;
}
mid=(l+r)/2;
if (x<a[mid]) mid--;
if (x==a[mid]) return mid;
return -1;
}
int Cbin2(int x)
{ int l=1,r=n,mid;
while(l<r)
{ mid=(l+r)/2;
if (x>=a[mid]) l=mid+1; else r=mid-1;
}
mid=(l+r)/2;
if (x<a[mid]) mid--;
return mid;
}
int Cbin3(int x)
{ int l=1,r=n,mid;
while(l<r)
{ mid=(l+r)/2;
if (x>a[mid]) l=mid+1; else r=mid;
}
mid=(l+r)/2;
if (x>a[mid]) mid++;
return mid;
}
int main()
{ int i,tip,nr;
f>>n;
for(i=1;i<=n;i++) f>>a[i];
f>>m;
for(i=1;i<=m;i++)
{f>>tip>>nr;
if (tip==0) g<<Cbin(nr)<<"\n";
if (tip==1) g<<Cbin2(nr)<<"\n";
if (tip==2) g<<Cbin3(nr)<<"\n";
}
return 0;
}