// c & p monkey

#include <stdio.h>

#define SIZE 100005

int N, X[SIZE], Q;

int main()
{
	freopen("cautbin.in", "r", stdin);
	freopen("cautbin.out", "w", stdout);

	scanf("%d", &N);
	
	int i, t, data, s, d, m, f;

	for(i = 1; i <= N; i++)
		scanf("%d", &X[i]);

	scanf("%d", &Q);
	
	while(Q)
	{
		scanf("%d%d", &t, &data);
		
		switch(t)
		{
			case 0:
			{
				s = 1;
				d = N;
				f = 0;
				while(d-s >= 2)
				{
					m = (s+d)/2;
				
					if(data < X[m])
						d = m;
					else
						s = m;
				}

				while((s < d || X[s] == data) && X[s+1] == data)
				{
					s++;
				}
			
				if(X[s] == data)
					printf("%d\n", s);
				else
					printf("-1\n");

				break;
			}

                        case 1:
                        {
                                s = 1;
                                d = N;
                                f = 0;
                                while(d-s >= 2)
                                {
                                        m = (s+d)/2;

                                        if(data < X[m])
                                                d = m;
                                        else
                                                s = m;
                                }

                                while(s <= d)
                                {
					if(X[d] <= data)
					{
						printf("%d\n", d);
						break;
					}
                                        d--;
                                }


                                break;
                        }

                        case 2:
                        {
                                s = 1;
                                d = N;
                                f = 0;
                                while(d-s >= 2)
                                {
                                        m = (s+d)/2;

                                        if(data < X[m])
                                                d = m;
                                        else
                                                s = m;
                                }

                                while(s <= d)
                                {
                                        if(X[s] >= data)
                                        {
                                                printf("%d\n", s);
                                                break;
                                        }
                                        s++;
                                }


                                break;
                        }
			
			
		}
		
		Q--;
	}

	return 0;
}