（交朋友）根据社会学研究表明，人们都喜欢找和自己身高相近的人

（交朋友）根据社会学研究表明，人们都喜欢找和自己身高相近的人做朋友。现在有n名身高两两不相同的同学依次走入教室，调查人员想预测每个人在走入教室的瞬间最想和已经进入教室的哪个人做朋友。当有两名同学和这名同学的身高差一样时，这名同学会更想和高的那个人做朋友。比如一名身高为1.80米的同学进入教室时，有一名身高为1.79米的同学和一名身高为1.81米的同学在教室里，那么这名身高为1.80米的同学会更想和身高为1.81 米的同学做朋友。对于第一个走入教室的同学我们不做预测。
由于我们知道所有人的身高和走进教室的次序，所以我们可以采用离线的做法来解决这样的问题，我们用排序加链表的方式帮助每一个人找到在他之前进入教室的并且和他身高最相近的人。（第一空 2 分，其余 3 分）

const
  maxn = 200000;
  infinity = 2147483647;
var
  answer, height, previous, next : array[0..maxn] of longint;
  rank : array[0..maxn] of longint;
  n, higher, shorter, i : longint;
procedure sort(l, r : longint);
var
  x, i, j, temp : longint;
begin
  x := height[rank[(l + r) div 2]];
  i := l;
  j := r;
  while i <= j do
  begin
    while height[rank[i]] < x do inc(i);
    while height[rank[j]] > x do dec(j);
    if    1    then
    begin
      temp := rank[i];
      rank[i] := rank[j];
      rank[j] := temp;
      inc(i);
      dec(j);
    end;
  end;
  if i < r then sort(i, r);
  if l < j then sort(l, j);
end;
begin
  readln(n);
  for i := 1 to n do
  begin
    read(height[i]);
    rank[i] := i;
  end;
  sort(1, n);
  for i := 1 to n do
  begin
    previous[rank[i]] := rank[i - 1];
    2;
  end;
  for i := n downto 2 do
  begin
    higher := infinity;
    shorter := infinity;
    if previous[i] <> 0 then
      shorter := height[i] - height[previous[i]];
    if next[i] <> 0 then
      3;
    if      4       then
      answer[i] := previous[i]
    else
      answer[i] := next[i];
    next[previous[i]] := next[i];
    5;
  end;
  for i := 2 to n do
    writeln(i, ':', answer[i]);
end.