#include<stdio.h>

int n,m,a[100005],i;

int cautbin0(int x)
{
	int st=1,dr=n,mij=0;
	while(st<=dr)
	{
		mij=(st+dr)/2;
		if((x==a[mij]&&x<a[mij+1])||(x==a[mij]&&mij==n+1)) return mij;
		else if(x<=a[mij]&&x<=a[mij+1]) st=mij+1;
		else dr=mij-1;
	}
	return -1;
}

int cautbin1(int x)
{
	int st=1,dr=n,mij=0;
	while(st<=dr)
	{
		mij=(st+dr)/2;
		if((a[mij]<=x&&a[mij+1]>x)||(a[mij]<=x&&mij+1==n+1)) return mij;
		else if(a[mij]<=x&&a[mij+1]<=x) st=mij+1;
		else dr=mij-1;
	}
	return 0;
}

int cautbin2(int x)
{
	int st=1,dr=n,mij=0;
	while(st<=dr)
	{
		mij=(st+dr)/2;
		if((a[mij]>=x&&a[mij-1]<x)||(a[mij]>=x&&mij-1==0)) return mij;
		else if(a[mij]>=x&&a[mij]>=x) dr=mij-1;
		else st=mij+1;
	}
	return 0;
}

int main()
{
	freopen("cautbin.in","r",stdin);
	freopen("cautbin.out","w",stdout);
	
	scanf("%d",&n);
	for(i=1;i<=n;++i) scanf("%d",&a[i]);
	scanf("%d",&m);
	
	for(i=1;i<=m;++i)
	{
		int x,nr,k;
		scanf("%d %d",&nr,&x);
		if(nr==0)
		{
			k=cautbin0(x);
			printf("%d\n",k);
		}
		if(nr==1)
		{
			k=cautbin1(x);
			printf("%d\n",k);
		}
		if(nr==2)
		{
			k=cautbin2(x);
			printf("%d\n",k);
		}
	}
	
	fclose(stdin);
	fclose(stdout);
	
	return 0;
}