← 返回题目列表

Codeforces · 976/D

D. 度数设置

中文机器翻译题面 查看原题

给定一个由 n 个正整数 d1, d2, ..., dn (d1 < d2 < ... < dn) 组成的序列。您的任务是构造一个无向图,使得:

- 正好有 dn + 1 个顶点;
- 没有自环;
- 没有多重边;
- 边数不超过 106 条;
- 其度数集等于 d。

顶点编号应为 1 到 (dn + 1)。

度数序列是一个数组 a,其长度等于图中的顶点数,其中 ai 是与第 i 个顶点相邻的顶点数。

度数集是度数序列中所有不同值的按升序排序的序列。

保证存在这样一个图,所有条件都成立,并且它包含的边不超过106条。

打印结果图。

输入

第一行包含一个整数 n (1 ≤ n ≤ 300) — 度数集的大小。

第二行包含 n 个整数 d1, d2, ..., dn (1 ≤ di ≤ 1000, d1 < d2 < ... < dn) — 度数集。

输出

在第一行中打印一个整数 m (1 ≤ m ≤ 106) — 结果图中的边数。保证存在这样一个图,所有条件都成立,并且它包含的边不超过106条。

接下来的 m 行中的每一行都应包含两个整数 vi 和 ui (1 ≤ vi, ui ≤ dn + 1) — 第 i 条边的描述。

示例

输入 #1

3
2 3 4

输出 #1

8
3 1
4 2
4 5
2 5
5 1
3 2
2 1
5 3

输入 #2

3
1 2 3

输出 #2

4
1 2
1 3
1 4
2 3