using namespace std;
#include<cstdio>
#define nmax 100001
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);
    scanf("%d",&n);
    for(i=1;i<=n;i++)
	scanf("%d",&v[i]);
    scanf("%d",&m);
    for(i=1;i<=m;i++)
    {
	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;
}