题目描述

题目译自 PA 2018 Runda 1 Poddrzewo

给定一个长度为 $n$ 的序列 $a$。

构造一个结点数为 $k$ 的无根树，结点编号分别为 $1 \cdots k$。该树第 $i$ 个结点的度数为 $a_i$。

有可能无解，你可以进行如下操作来使其有解：

1. 修改序列中第 $i$ 个数。
2. 删除序列中第 $i$ 个数。
3. 交换序列中第 $i,j$ 个数。

可以证明，进行有限次操作后一定有解。

你的任务是 最小化操作 $1$ 使用的次数。

输入格式

一行一个整数 $n$，表示序列 $a$ 的长度。

下一行有 $n$ 个整数，第 $i$ 个整数表示 $a_i$。

输出格式

第一行一个整数 $x$ ，表示操作 $1$ 使用次数最小值。

第二行一个整数 $k\ (2 \le k \le n)$，表示你构造的树结点数目。

接下来 $k-1$ 行，每行两个数 $u,v\ (1 \le u, v \le k)$，表示连接第 $u,v$ 个结点。

多解输出任意解。

6
2 1 5 3 1 1

0
5
1 2
2 3
1 4
1 5

3
1 2 2

1
3
1 2
2 3

提示

样例 1 解释

我们可以删除第 $3$ 个数字，然后更改元素的顺序。

得到最后的序列为 $(3,2,1,1,1)$。

这是构造的树的示意图：

样例 2 解释

我们可以修改第 $3$ 个数字，得到最后的序列为 $(1,2,1)$。可以证明，操作 $1$ 至少需要使用 $1$ 次。

这是构造的树的示意图：

数据范围

本题采用捆绑测试

对于 $100\%$ 的数据：

• $2 \le n \le 10^6$
• $1 \le a_i \le n-1$

保证存在至少一个子任务，其中操作 $1$ 使用次数最小值为 $0$。