CF1242E.Planar Perimeter

Ujan has finally cleaned up his house and now wants to decorate the interior. He decided to place a beautiful carpet that would really tie the guest room together.

He is interested in carpets that are made up of polygonal patches such that each side of a patch is either a side of another (different) patch, or is an exterior side of the whole carpet. In other words, the carpet can be represented as a planar graph, where each patch corresponds to a face of the graph, each face is a simple polygon. The perimeter of the carpet is the number of the exterior sides.

Ujan considers a carpet beautiful if it consists of $f$ patches, where the $i$-th patch has exactly $a_i$ sides, and the perimeter is the smallest possible. Find an example of such a carpet, so that Ujan can order it!

乌詹终于打扫完了他的房子，现在想要装饰室内。他决定铺上一块漂亮的地毯，让客厅显得更加协调。

他感兴趣的是由多边形块拼接而成的地毯，其中每个块的每条边要么是另一个（不同的）块的一条边，要么是整块地毯的一条外边界。换句话说，该地毯可表示为一个平面图，其中每个块对应图中的一个面，且每个面均为一个简单多边形。地毯的周长定义为所有外边的数量。

乌詹认为一块地毯是“美丽的”，当且仅当它由 $f$ 个块组成，且第 $i$ 个块恰好有 $a_i$ 条边，同时其周长达到最小可能值。请构造出这样一块地毯的一个实例，以便乌詹可以下单订购！

The first line of input contains a single integer $f$ ($1 \leq f \leq 10^5$), the number of patches in the carpet.

The next line contains $f$ integers $a_1, \ldots, a_f$ ($3 \leq a_i \leq 3\cdot 10^5$), the number of sides of the patches. The total number of the sides of the patches $a_1 + \ldots + a_f$ does not exceed $3\cdot10^5$.

输入的第一行包含一个整数 $f$（$1 \leq f \leq 10^5$），表示地毯中补丁的数量。

下一行包含 $f$ 个整数 $a_1, \ldots, a_f$（$3 \leq a_i \leq 3\cdot 10^5$），表示各补丁的边数。所有补丁的边数总和 $a_1 + \ldots + a_f$ 不超过 $3\cdot10^5$。

Output the description of the carpet as a graph.

First, output a single integer $n$ ($3 \leq n \leq 3 \cdot 10^5$), the total number of vertices in your graph (the vertices must be numbered from $1$ to $n$).

Then output $f$ lines containing the description of the faces. The $i$-th line should describe the $i$-th face and contain $a_i$ distinct integers $v_{i,1}, \ldots, v_{i,a_i}$ ($1 \leq v_{i,j} \leq n$), which means that the vertices $v_{i,j}$ and $v_{i,(j \bmod{a_i})+1}$ are connected by an edge for any $1 \leq j \leq a_i$.

The graph should be planar and satisfy the restrictions described in the problem statement. Its perimeter should be the smallest possible. There should be no double edges or self-loops in the graph. The graph should be connected. Note that a solution always exists; if there are multiple solutions, output any of them.

以图的形式输出地毯的描述。

首先，输出一个整数 $n$（$3 \leq n \leq 3 \cdot 10^5$），表示图中顶点的总数（顶点编号必须为 $1$ 到 $n$）。

然后输出 $f$ 行，每行描述一个面。第 $i$ 行描述第 $i$ 个面，包含 $a_i$ 个互不相同的整数 $v_{i,1}, \ldots, v_{i,a_i}$（$1 \leq v_{i,j} \leq n$），其含义是：对任意 $1 \leq j \leq a_i$，顶点 $v_{i,j}$ 与 $v_{i,(j \bmod{a_i})+1}$ 之间存在一条边。

该图必须是平面图，并满足题目陈述中所述的所有限制条件。其周长应尽可能小。图中不得存在重边或自环。图必须连通。注意：解一定存在；若存在多个解，输出其中任意一个即可。

In the first sample, the two triangular faces are connected by a single edge, which results in the minimum perimeter $4$.

The figure shows one possible configuration for the second sample. The minimum perimeter in this case is $3$.

在第一个样例中，两个三角形面通过一条公共边相连，从而得到最小周长 $4$。

下图展示了第二个样例的一种可能构型。此时的最小周长为 $3$。