using namespace std;
#include<cstdio>
#define nmax 100001
#define dim 8192

char ax[dim];
int pz;

inline void cit(int &x)
{
	x=0;
	while(ax[pz] < '0' && ax[pz] > '9')
		if(++pz == dim) fread(ax,1,dim,stdin),pz=0;
	
	while(ax[pz] >= '0' && ax[pz] <= '9')
	{
		x=x*10+ax[pz]-'0';
		if(++pz == dim) fread(ax,1,dim,stdin),pz=0;
	}
}

int v[nmax],n,m,x,k,i;


int cb1(int x)
{
    int s,f,mij;
    for(s=1,f=n;s<=f;)
    {
	mij=s+(f-s)/2;
	if(x<v[mij]) f=mij-1;
	else if(x>v[mij]) s=mij+1;
	else return mij;
    }
    return -1;
}

int cb2(int x)
{
    int s,f,mij,poz=1;
    for(s=1,f=n;s<=f;)
    {
	mij=s+(f-s)/2;
	if(v[mij]<=x) {poz=mij; s=mij+1;}
	else f=mij-1;
    }
    return poz;
}

int cb3(int x)
{
    int s,f,mij,poz=n;
    for(s=1,f=n;s<=f;)
    {
	mij=s+(f-s)/2;
	if(v[mij]>=x) {poz=mij; f=mij-1;}
	else s=mij+1;
    }
    return poz;
}
int main()
{
    freopen("cautbin.in","r",stdin);
    freopen("cautbin.out","w",stdout);
    cit(n);
	//scanf("%d",&n);
    for(i=1;i<=n;i++)cit(v[i]);
	//scanf("%d",&v[i]);
	 cit(m);
	//   scanf("%d",&m);
    for(i=1;i<=m;i++)
    {
		cit(k); cit(x);
	//scanf("%d%d",&k,&x);
	if(!k) printf("%d\n",cb1(x));
	else if(k==1) printf("%d\n",cb2(x));
	else printf("%d\n",cb3(x));
    }
    return 0;
}