#include<iostream>
#include<fstream>
using namespace std;
int alegere(int ls,int ld,int x,int v[100000])
{if(ls>ld)
	return -1;
if(v[(ls+ld)/2]==x)
	return (ls+ld)/2;
else
{int nr=(ls+ld)/2;
if(v[nr]>x)
	return alegere(ls,ld-1,x,v);
else
	return alegere(ls+1,ld,x,v);
}
}
int main()
{int n,m,v[100000],k,poz,j,i,ls,ld,y,x;
ifstream f("cautbin.in");
ofstream g("cautbin.out");
f>>n;
for(i=1;i<=n;i++)
	f>>v[i];
f>>m;
for(i=1;i<=m;i++)
{f>>x>>y;k=alegere(1,n,y,v);
if(x==0)
{poz=k;
if(poz!=-1)
  {for(j=k+1;j<=n;j++)
	if(v[j]==y)
		poz=j;
	else
		j=n;
	g<<poz<<'\n';
  }
}
if(x==1)
{
if(k!=-1)
{for(j=k+1;j<=n;j++)
	if(v[j]==y)
		poz=j;
	else
		j=n;
	g<<poz<<'\n';
}
else
	{ls=1;ld=n;k=(ls+ld)/2;
		while(ls<=ld&&v[k]>y)
		k=(ls+ld)/2;
		g<<k<<'\n';
	}
}


if(x==2)
{
	if(k!=-1)
     {for(j=k-1;j>=1;j--)
            if(v[j]==y)
                poz=j;				
    g<<poz<<'\n';
	 }
	 else
		 {ls=1;ld=n;k=(ls+ld)/2;
		while(ls<=ld&&v[k]<y)
		k=(ls+ld)/2;
		g<<k<<'\n';
		 }
}
}

f.close();
g.close();
return 0;
}