← 返回题目列表

Codeforces · 1214/E

E. Petya 和建筑套装

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

这是 Petya 的生日聚会,他的朋友们给了他一套全新的“电工-$$$n$$$”建筑套装,他们相信他会喜欢这个套装,就像他总是喜欢他们给他的奇怪谜题一样。

搭建套装“电工-$$$n$$$”由 $$$2n - 1$$$ 电线和 $$$2n$$$ 灯泡组成。每个灯泡都有自己的唯一索引,该索引是从 $$$1$$$ 到 $$$2n$$$ 的整数,而所有电线看起来都相同并且无法区分。为了完成这套结构,必须使用每根电线连接两个不同的灯泡。我们将完整的构造集中的链定义为长度至少为两个的不同灯泡的序列,使得该序列中的每两个连续灯泡直接通过电线连接。如果灯泡和电线的最终网络具有树结构,即任何两个不同的灯泡是某个链的端点,则完整的构造集配置被认为是正确的。

Petya 花了几天时间组装不同的配置,他注意到有时有些灯泡会亮。经过一系列实验后,他得出了这样的结论:如果连接灯泡的链条恰好由 $$$d_i$$$ 电线组成,则索引为 $$$2i$$$ 和 $$$2i - 1$$$ 的灯泡就会打开。此外,以下重要条件成立:$$$d_i$$$ 的值永远不会大于$$$n$$$。

Petya 已尽力但无法找到使所有灯泡都打开的配置,因此他寻求您的帮助。请找出一种使所有灯泡都发光的配置。保证这样的配置始终存在。

输入

输入的第一行包含一个整数 $$$n$$$ ($$$1 \leq n \leq 100\,000$$$) - 定义灯泡数量和电线数量的构造集参数。

下一行包含 $$$n$$$ 整数 $$$d_1, d_2, \ldots, d_n$$$ ($$$1 \leq d_i \leq n$$$),其中 $$$d_i$$$ 代表灯泡 $$$2i$$$ 和 $$$2i - 1$$$ 之间的链条应包含的电线数量。

输出

打印 $$$2n - 1$$$ 行。其中第 $$$i$$$ 应包含两个不同的整数 $$$a_i$$$ 和 $$$b_i$$$ ($$$1 \leq a_i, b_i \leq 2n$$$, $$$a_i \ne b_i$$$) - 通过电线连接的灯泡的索引。

如果有多个可能的有效答案,您可以打印其中任何一个。

示例

输入 #1

3
2 2 2

输出 #1

1 6
2 6
3 5
3 6
4 5

输入 #2

4
2 2 2 1

输出 #2

1 6
1 7
2 6
3 5
3 6
4 5
7 8

输入 #3

6
2 2 2 2 2 2

输出 #3

1 3
2 3
3 5
4 5
5 7
6 7
7 12
8 12
9 11
9 12
10 11

输入#4

2
1 1

输出#4

1 2
1 4
3 4

注意

第一个样本测试的答案。

第二个样本测试的答案。