#include<fstream>
using namespace std;
#define NMAX 100010

int n,m;
int a[NMAX];
int elem,poz;

void cautare0(int st, int dr)
{
 int mijl = (dr - st) / 2 + st;
 if (st <= dr)
	{
	 if (a[mijl] == elem)
		poz = max(poz, mijl);
	 if (a[mijl] <= elem)
		 cautare0(mijl+1, dr); else
		 cautare0(st, mijl-1);
	}
}

void cautare1(int st, int dr)
{
 int mijl = (dr - st) / 2 + st;
 if (st <= dr)
	 if (a[mijl] <= elem)
		{
		 poz = max(poz, mijl);
		 cautare1(mijl+1, dr);
		} else
		cautare1(st, mijl-1);
}

void cautare2(int st, int dr)
{
 int mijl = (dr - st) / 2 + st;
 if (st <= dr)
	 if (a[mijl] >= elem)
		{
		 poz = min(poz, mijl);
		 cautare2(st, mijl-1);
		} else
		cautare2(mijl+1, dr);
}

void read_solve()
{
 int i,op;
 ifstream fin("cautbin.in");
 ofstream fout("cautbin.out");
 fin>>n;
 for (i=1; i<=n; ++i)
	 fin>>a[i];
 fin>>m;
 for (i=1; i<=m; ++i)
	{
	 fin>>op>>elem;
	 if (op == 0)
		{
		 poz = -1;
		 cautare0(1, n);
		} else
		if (op == 1)
		   {
			poz = -1;
			cautare1(1, n);
		   } else
		   {
			poz = n + 1;
			cautare2(1, n);
		   }
	 fout<<poz<<'\n';
	}
 fin.close();
 fout.close();
}

int main()
{
 read_solve();
 return 0;
}