#include <bits/stdc++.h>
using namespace std;
ifstream fin("cautbin.in");
ofstream fout("cautbin.out");
int A[100100];
int main () {
    int i, n, m, tip, x;
    fin>>n;
    for (i = 1; i <= n; ++ i) fin>>A[i];
    fin>>m;
    while (m){
          fin>>tip>>x;
          if (tip == 0)
             {
             	int p=1, u=n, mid;
             	while(p<=u){
             		mid=(p+u)/2;
             		if(A[mid]<=x) p=mid+1;
             		else u=mid-1;
				 }
				 mid=(p+u)/2;
				 if(A[mid]>x) mid--;
				 if(A[mid]==x) fout<<mid<<'\n';
					else fout<<-1<<'\n';
			 }
         if (tip == 1)
             {
             	int p=1, u=n, mid;
             	while(p<u){
             		mid=(p+u)/2;
             		if(A[mid]<=x) p=mid+1;
             		else u=mid;
				 }
				 mid=(p+u)/2;
				 if(A[mid]>x) mid--;
				 fout<<mid<<'\n';
             }
          if (tip == 2)
             {
             	int p=1, u=n, mid;
             	while(p<u){
             		mid=(p+u)/2;
             		if(A[mid]<x) p=mid+1;
             		else u=mid;
				 }
				 mid=(p+u)/2;
				 if(A[mid]<x) mid++;
				 fout<<mid<<'\n';
             }
             m--;
    }
}