#include<iostream>
#include<fstream>
using namespace std;

long long x[100000];
int xc;

int cautare(long long st, long long dr)
{
	long long m,mij;
	while(dr>st)
	{
		m=(dr+st)/2;
		mij=x[m];
		
		if(mij==xc) return m;
		if(mij>xc) dr=m-1;
		if(mij<xc) st=m+1;
	}
	return 0;
}

int main()
{
	ifstream f("cautbin.in");
	ofstream g("cautbin.out");
	
	long long n;
	int i,w,m,ok,t;
	
	f>>n;
	for( i=1;i<=n;i++)
		f>>x[i];
	f>>t;
	for( i=1;i<=t;i++)
	{
		f>>w>>xc;
		if(w==0)
		{
			m=cautare(x[1],x[n]);
			if(!cautare(x[1],x[n]))
				cout<<-1;
			else
			{
				while(xc==x[m])
					m++;
				g<<m-1<<endl;
			}
		}
		if(w==1)
		{
			
			 ok=1;
			while(ok==1)
			{
				if(!cautare(x[1],x[n]))
					{
						xc--;
						cautare(x[1],x[n]);
				    }
				else 
					{
						ok=0;
						m=cautare(x[1],x[n]);
					}
			}
			while(xc==x[m])
				m++;
			g<<m-1<<endl;
		}
		if(w==2)
		{
			ok=1;
			while(ok==1)
			{
				if(!cautare(x[1],x[n]))
				{
					xc++;
					cautare(x[1],x[n]);
				}
				else
				{
					ok=0;
					m=cautare(x[1],x[n]);
				}
			}
			while(xc==x[m])
				m--;
			g<<m+1<<endl;
		}
	}
}