const maxn=100000;
      fin='cautbin.in';
      fout='cautbin.out';
var n,m,x,int,i:longint;
    v:array[1..maxn] of longint;
    f,g:text;

procedure binar0 (li,lo:longint);
var mij:longint;
begin
  if (li>=lo) then
  begin
     if x=v[li] then
        writeln(g,li)
     else
        writeln(g,-1);
     exit;
  end
  else
  begin
  mij:=(li+lo) div 2;
  if x=v[mij] then
  begin
      writeln(g,mij);
      exit;
  end
  else
      if x>v[mij] then
          binar0(mij+1,lo)
      else
          binar0(li,mij-1);
  end;
end;

procedure binar1 (li,lo:longint);
var mij:longint;
begin
  if (li>=lo) then
  begin
     writeln(g,li);
     exit;
  end
  else
  begin
  if (li+lo) mod 2=1 then
    mij:=(li+lo) div 2+1
  else
    mij:=(li+lo) div 2;
  if x>=v[mij] then
  begin
      binar1(mij,lo);
      exit;
  end
  else
      binar1(li,mij-1);
  end;
end;

procedure binar2 (li,lo:longint);
var mij:longint;
begin
  if (li>=lo) then
  begin
     writeln(g,li);
     exit;
  end
  else
  begin
  mij:=(li+lo) div 2;
  if x>v[mij] then
  begin
      binar2(mij+1,lo);
      exit;
  end
  else
      binar2(li,mij);
  end;
end;


begin
assign(f,fin);
assign(g,fout);
rewrite(g);
reset(f);
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,int,x);
if int=0 then
binar0(1,n);
if int=1 then
binar1(1,n);
if int=2 then
binar2(1,n);
end;
close(f);
close(g);
end.