#include<iostream>
#include<fstream>
using namespace std;
ifstream fin("cautbin.in");
ofstream fout("cautbin.out");


int n,m,a[1000001];

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


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

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



int main(){
	fin>>n;
	for(int i=1;i<=n;++i){fin>>a[i];}
	fin>>m;
	for(int i=1;i<=m;++i){
		int c,x;
		fin>>c>>x;
		if(c==0)
			fout<<cautaBin0(x)<<"\n";
		if(c==1)
			fout<<cautaBin1(x)<<"\n";
		if(c==2)
			fout<<cautaBin2(x)<<"\n";
		

	}
	
	
	
	
	
	
}