#include<cstdio>

using namespace std;
int n,M,m,v[100010],l,r,i,nr,cod;
void read(),solve();
int main()
{
	read();
	solve();
	return 0;
}
void read()
{
	freopen("cautbin.in","r",stdin);
	freopen("cautbin.out","w",stdout);
	scanf("%d",&n);
	for(i=1;i<=n;i++)
		scanf("%d",&v[i]);
	scanf("%d",&M);
}
void solve()
{
	for(;M;M--)
	{
		scanf("%d%d",&cod,&nr);
		if(cod==0)
		{
			if(nr>v[n])
			{
				printf("-1\n");
				continue;
			}
			if(nr==v[n])
			{
				printf("%d",n);
				continue;
			}
			l=1;r=n;
			for(;;)
			{
				m=(l+r)/2;
				if(v[m]==nr)
					if(v[m+1]==nr)
					{
						l=m;continue;
					}
					else
					{
						printf("%d\n",m);
						break;
					}
				else
					if(v[m]>nr)
					{
						r=m;
						continue;
					}
					else
					{
						l=m;continue;
					}
			}
			continue;
		}
		if(cod==1)
		{
			if(nr>=v[n])
			{
				printf("%d\n",n);
				continue;
			}
			l=1;r=n;
			for(;;)
			{
				m=(l+r)/2;
				if(v[m]<=nr)
					if(v[m+1]<=nr)
					{
						l=m;continue;
					}
					else
					{
						printf("%d\n",m);
						break;
					}
				else
				{
					r=m;
					continue;
				}
			}
			continue;
		}
		l=1;r=n;
		for(;;)
		{
			m=(l+r)/2;
			if(v[m]<nr)
			{
				l=m;continue;
			}
			else
			{
				if(v[m-1]<nr)
				{
					printf("%d\n",m);
					break;
				}
				else
				{
					r=m;
					continue;
				}
			}
		}
	}
}