小红的ds题
题号:NC294416
时间限制:C/C++/Rust/Pascal 1秒,其他语言2秒
空间限制:C/C++/Rust/Pascal 256 M,其他语言512 M
Special Judge, 64bit IO Format: %lld

题目描述

\hspace{15pt}小红希望你构造一棵层数为 n二叉树,其第 i 层恰好有 a_i 个节点。你能帮帮她吗?

\hspace{15pt}一棵树被称为二叉树,当且仅当其满足:
\hspace{23pt}\bullet\,每个节点要么没有父节点连接(此时该节点被称为根节点)、要么被 1 个父节点连接(此时该节点被称为父节点的子节点);
\hspace{23pt}\bullet\,每个节点连接的子节点数量要么为 0(此时该节点被称为叶子节点)、要么小于等于 2(此时该节点被称为分支节点)。

输入描述:

\hspace{15pt}第一行输入一个正整数 n \left(1 \leqq n \leqq 10^4\right),代表二叉树的层数。
\hspace{15pt}第二行输入 n 个正整数 a_1,a_2,\dots,a_n \left(1 \leqq a_i \leqq 10^5\right),代表二叉树的第 i 层的节点数量限制。保证 a_1 = 1,且对于 2 \leqq i \leqq n,均有 a_i \leqq a_{i-1} \times 2

\hspace{15pt}除此之外,保证单个测试文件的 a_i 之和不超过 10^5

输出描述:

\hspace{15pt}第一行输出一个正整数 p \left(1 \leqq p \leqq \textstyle\sum_{i=1}^n a_i\right),代表根结点的编号。编号从 1 开始。
\hspace{15pt}此后输出 \textstyle\sum_{i=1}^n a_i 行,第 i 行输出两个元素 l_i,r_i,分别代表 i 号节点的左儿子和右儿子的编号。特别的,如果不存在左儿子/右儿子,则输出 -1 替代这个编号。

\hspace{15pt}如果存在多个解决方案,您可以输出任意一个,系统会自动判定是否正确。注意,自测运行功能可能因此返回错误结果,请自行检查答案正确性。
示例1

输入

复制
3
1 2 3

输出

复制
4
-1 -1
1 -1
6 5
2 3
-1 -1
-1 -1

说明

image.png