2018 博士生面试机考

D. Equally-divided

单点时限: 1.0 sec

内存限制: 256 MB

个小朋友,标号为 ,每个小朋友有一些糖果,第 个小朋友拥有糖果数量为

为了使得每个小朋友拥有相同的糖果,现提供如下操作:选择两个小朋友组成一个有序对 ,然后记两个小朋友拥有的糖果总和为 ,然后令 ,

即:

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

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

输入格式

第一行一个整数

第二行 个整数用空格隔开:

部分分约定:

  • : .
  • : .
  • : .

输出格式

如果不可能,输出一行 Impossible

否则:

  • 第一行:输出一个整数 ,表示操作序列的长度。
  • 接下来依次输出操作,每一行输出两个整数 的含义见题意。

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

样例

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