#include <bits/stdc++.h>
using namespace std;
#define Nmax 100013
int op,n,i,m,a;
int V[Nmax];

int upper_bound(int left, int right,int nr,int ind)
 { 
  int poz(0);
  while(left<=right)
    {
	 int middle=(left+right)/2;
     if (V[middle]<=nr) 
	        {
			left=middle+1;
			poz=middle;
		    }
        else right=middle-1;
	}
  if (V[poz]!=a && ind==0 ) return -1;
  return poz;
 }

int lower_bound(int left, int right,int nr)
 { 
  int poz(0);
  while(left<=right)
    {
	 int middle=(left+right)/2;
     if (V[middle]>=nr) 
	        {
			right=middle-1;
			poz=middle;
		    }
        else left=middle+1;
	}
  return poz;
 }

int main(void)
{
 ifstream in("cautbin.in");
 ofstream out("cautbin.out");
 in>>n;
 for (i=1;i<=n;++i)	 
   in>>V[i];
 in>>m;
  while(m--)
    {
     in>>op>>a;
     if (op==0) out<<upper_bound(1,n,a,0)<<"\n";
     if (op==1) out<<upper_bound(1,n,a,1)<<"\n";
     if (op==2) out<<lower_bound(1,n,a)<<"\n";
    }
 return 0;
}