#include<fstream>
using namespace std;
ifstream f("cautbin.in");
ofstream g("cautbin.out");
long sir[100001],n,deci,x,m;
void citire()
{ for(int i=1;i<=n;i++)
	f>>sir[i];
}
void solve()
{ int st=1,dr=n,mijl,sol=0;
  bool ok=0;
  f>>deci>>x;
  if(deci==0)
  { while(st<=dr)
	{ mijl = st + (dr-st)/2;
	  if(sir[mijl]==x)
	  { st=mijl+1;
	    sol=mijl;
		ok=1;
	  }
	  else
		if(sir[mijl]<x)
			st=mijl+1;
		else
			dr=mijl-1;
	}
	if(ok==0)
		g<<-1<<'\n';
	else
	g<<sol<<'\n';
  }
  else
	if(deci==1)
	{ while(st<=dr)
	  { mijl = st + (dr-st)/2;
		if(sir[mijl]<=x)
		{ st=mijl+1;
		  sol=mijl;
		}
		else
		dr=mijl-1;
	  }
	g<<sol<<'\n';
	}
	else
	{ while(st<=dr)
	  { mijl = st + (dr-st)/2;
		if(sir[mijl]>=x)
		{ dr=mijl-1;
		  sol=mijl;
		}
		else
			st=mijl+1;
	  }
	g<<sol<<'\n';
	}
} 
int main()
{ f>>n;
  citire();
  f>>m;
  for(int i=1;i<=m;i++)
	solve();
  f.close();
  g.close();
  return 0;
}