#include<stdio.h>

int n, v[102400];

int cautbin1(int a)
{
	int st=1, dr=n, mij;
	while(st<=dr)
	{
		mij=(st+dr)/2;
		if (v[mij] == a)
			return mij;
		if (v[mij] < a)
			st=mij+1;
		else
			dr=mij-1;
	}
	if (v[mij]!=a)
		return -1;
	return mij;
}

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

int cautbin3(int a)
{
	int st=1, dr=n, mij;
	while(st<dr)
	{
		mij=(st+dr)/2;
		if (v[mij] >= a)
			dr=mij;
		if (v[mij] <a)
			st=mij+1;
	}
	mij=(st+dr)/2;
	if (v[mij] < a)
		++mij;	
	return mij;
}

/*
int cautbin1(int a)  
{  
    int st=1, dr=n, mij;  
    while(st<dr)  
    {  
        mij=(st+dr)/2;  
        if (v[mij] > a)  
            dr=mij-1;  
        if (v[mij] <= a)  
            st=mij+1;  
    }  
    if (v[st]!=a)  
        return -1;  
    return st;  
}  
  
int cautbin2(int a)  
{  
    int st=1, dr=n, mij;  
    while(st<dr)  
    {  
        mij=(st+dr)/2;  
        if (v[mij] >a)  
            dr=mij-1;  
        if (v[mij] <= a)  
            st=mij+1;  
    }  
    if (v[st]>a)  
        return st-1;  
    return st;  
}  
  
int cautbin3(int a)  
{  
    int st=1, dr=n, mij;  
    while(st<dr)  
    {  
        mij=(st+dr)/2;  
        if (v[mij] >= a)  
            dr=mij;  
        if (v[mij] < a)  
            st=mij+1;  
    }  
	if (v[st]<a)  
        return st+1;  
    return st;  
}
*/
int main()
{
	freopen("cautbin.in", "r", stdin);
	freopen("cautbin.out", "w", stdout);
	
	int i, a, b, m;
	
	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", &a, &b);
		switch (a)
		{
			case 0:
				printf("%d\n", cautbin1(b));
			break;
			case 1:
				printf("%d\n", cautbin2(b));
			break;
			case 2:
				printf("%d\n", cautbin3(b));
			//	printf("err\n");
			break;
			default:
			//nu va intra aici
			break;
		}
	}
	fclose(stdout);
	return 0;
}