// 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
while (lo <= hi) do
        begin
        mi := lo + (hi - lo) div 2;
        if (v[mi]=x) then
                begin
                liCBinExist := mi;
                exit;
                end
        else
                if (x > v[mi]) then lo := mi+1
                else                hi := mi-1;
        end;
liCBinExist := -1;
end;

function        liCBinLower     (x, lo, hi : longint) : longint;
var mi, glx : longint;  // glx = greatest number lower than x
begin

while (lo <= hi) do
        begin
        mi := lo + (hi - lo) div 2;
        if (v[mi]=x) then
                begin
                liCBinLower := mi;
                exit;
                end
        else
                if (x > v[mi]) then begin lo := mi+1; glx := mi; end
                else                hi := mi-1;
        end;
liCBinLower := glx;

end;


function        liCBinGreat     (x, lo, hi : longint) : longint;
var mi, lgx : longint;  // lgx = lowest number greater than x
begin
while (lo <= hi) do
        begin
        mi := lo + (hi - lo) div 2;
        if (v[mi]=x) then
                begin
                liCBinGreat := mi;
                exit;
                end
        else
                if (x > v[mi]) then lo := mi+1
                else                begin hi := mi-1; lgx := mi; end;
        end;
liCBinGreat := lgx;
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.