#include <fstream>
using namespace std;
ifstream cin("cautbin.in");
ofstream cout("cautbin.out");
int n,v[100001];

int c0(int x)
{int st=1,dr=n,poz=-1,mij;
while(st<=dr)
{mij=(st+dr)/2;
if(v[mij]>x) dr=mij-1;
else {if(v[mij]==x) poz=mij; st=mij+1;}}
return poz;}

int c1(int x)
{int st=1,dr=n,poz=-1,mij;
while(st<=dr)
{mij=(st+dr)/2;
if(v[mij]>x) dr=mij-1;
else{poz=mij; st=mij+1;}}
return poz;}

int c2(int x)
{int st=1,dr=n,poz=-1,mij;
while(st<=dr)
{mij=(st+dr)/2;
if(v[mij]<x) st=mij+1;
else {poz=mij; dr=mij-1;}}
return poz;}

int i,m,c,x;
int main()
{cin>>n;
for(i=1;i<=n;i++)
cin>>v[i];
cin>>m;
for(i=1;i<=m;i++)
{cin>>c>>x;
if(c==0) cout<<c0(x)<<'\n';
else if(c==1) cout<<c1(x)<<'\n';
else cout<<c2(x)<<'\n';}
return 0;}