// Arhiva educationala - Cautare   Binara
//
// mi = lo + (hi-lo) div 2
// in loc de
// mi = (lo + hi) div 2

var     n,m,t,x,i : longint;
        v       : array [1..100000] of longint;
        f,g     : text;

function        liCBinExist     (x, lo, hi : longint) : longint;
var mi : longint;
begin
mi := lo + (hi - lo) div 2;
if mi < lo then begin liCBinExist := -1; exit; end;
if mi > hi then begin liCBinExist := -1; exit; end;
if (v[mi] = x) then
        liCBinExist := mi
else
        if (x > v[mi]) then
                liCBinExist := liCBinExist (x, mi+1, hi)
        else
                liCBinExist := liCbinExist (x, lo, mi-1);
end;

function        liCBinLower     (x, lo, hi : longint) : longint;
var mi : longint;
begin
mi := lo + (hi - lo) div 2;
if mi < lo then begin liCBinLower := mi; exit; end;
if mi > hi then begin liCBinLower := hi; exit; end;
if (v[mi] = x) then
        liCBinLower := mi
else
        if (x > v[mi]) then
                liCBinLower := liCBinLower (x, mi+1, hi)
        else
                liCBinLower := liCbinLower (x, lo, mi-1);
end;


function        liCBinGreat     (x, lo, hi : longint) : longint;
var mi : longint;
begin
mi := lo + (hi - lo) div 2;
if mi < lo then begin liCBinGreat := lo; exit; end;
if mi > hi then begin liCBinGreat := mi; exit; end;
if (v[mi] = x) then
        liCBinGreat := mi
else
        if (x > v[mi]) then
                liCBinGreat := liCBinGreat (x, mi+1, hi)
        else
                liCBinGreat := liCbinGreat (x, lo, mi-1);
end;



begin
assign  (f, 'cautbin.in');
assign  (g, 'cautbin.out');
reset   (f);
rewrite (g);
readln  (f, n);
for i:=1 to n do
  read(f, v[i]);
readln  (f);
readln  (f, m);
for i:=1 to m do
  begin
  readln(f, t, x);
  case  t of
   0: writeln (g, liCBinExist(x, 1, n));
   1: writeln (g, liCBinLower(x, 1, n));
   2: writeln (g, liCBinGreat(x, 1, n));
  end;
  end;
close   (f);
close   (g);
end.