2018 博士生面试机考

D. Equally-divided

单点时限: 1.0 sec

内存限制: 256 MB

有 $n$ 个小朋友,标号为 $1$ 到 $n$,每个小朋友有一些糖果,第 $i$ 个小朋友拥有糖果数量为 $a_i$。

为了使得每个小朋友拥有相同的糖果,现提供如下操作:选择两个小朋友组成一个有序对 $(u,v)$ $(1 \le u,v \le n, u \ne v)$,然后记两个小朋友拥有的糖果总和为 $S$,然后令 $a_u=\lfloor \frac{S}{2} \rfloor$, $a_v=\lceil \frac{S}{2} \rceil$。

即:

function do_something(u, v):
    S := (a[u] + a[v])
    a[u] := floor(S / 2)
    a[v] := ceil(S / 2)

请构造一系列操作,使得所有小朋友最终拥有相同的糖果。或者判断出这是不可能的。

输入格式

第一行一个整数 $n$。

第二行 $n$ 个整数用空格隔开:$a_1,a_2,\ldots,a_n$。

部分分约定:

  • $30\%$: $1 \le n \le 10, 0 \le a_i \le 10$.
  • $60\%$: $1 \le n \le 10, 0 \le a_i \le 10^9$.
  • $100\%$: $1 \le n \le 1~000, 0 \le a_i \le 10^9$.

输出格式

如果不可能,输出一行 Impossible

否则:

  • 第一行:输出一个整数 $m$ $(0 \le m \le 10~000)$,表示操作序列的长度。
  • 接下来依次输出操作,每一行输出两个整数 $u,v$,$u,v$ 的含义见题意。

所以你的程序应该在 $10~000$ 步以内完成任务。给定数据保证存在一种方案能够完成目标,除非不可能完成。

样例

Input
4
1 3 1 3
Output
2
1 2
3 4