当你逃离一只想要和你玩耍和/或把你当作晚餐吃掉的熊时，识别它的种类非常重要： 如果你一直跑，找到一棵树并爬上去，而熊跟在你后面，那是棕熊； 如果你一直跑，找到一棵树并爬上去，而熊把你从树上摇下来，那是灰熊； * 如果你一直跑却找不到树，那是北极熊。

因此，让我们专注于寻找一棵树。在计算机科学中，树仅仅是一个包含 $k$ 个顶点和 $k-1$ 条边的集合，其中每条边连接两个顶点。这些连接必须保证从任何一个顶点出发，仅通过边就能到达其他任何顶点。从一个顶点出发的边的数量称为该顶点的度数。

给定一个包含 $n$ 个整数的序列 $a_1, a_2, \dots, a_n$。你怀疑这是某棵树所有顶点的度数列表。不幸的是，一些随机数字混入了序列，此外，还有一些数字在过程中被错误地改写了。请从序列中删除不必要的数字并修改其他一些数字，使其成为一个正确的度数列表。

形式上，你可以改变给定 $n$ 个数字序列中元素的顺序，删除其中的一些元素，然后修改剩余元素中的一部分。对于得到的序列 $d_1, d_2, \dots, d_k$，你必须给出一棵具有 $k \ge 2$ 个顶点（编号从 $1$ 到 $k$）的树，使得 $d_i$ 是第 $i$ 个顶点的度数。被删除和被修改的顶点数量可以是任意的（也可以为 $0$）——你的任务是找到一个修改顶点数量最少的解决方案。

输入格式

输入的第一行包含一个整数 $n$ ($2 \le n \le 10^6$)，表示序列中元素的数量。下一行包含一个由 $n$ 个整数组成的序列 $a_1, a_2, \dots, a_n$ ($1 \le a_i \le n-1$)。

输出格式

在第一行中，输出修改元素的数量 $x$（你需要最小化该值）。在第二行中，输出树的大小 $k$ ($2 \le k \le n$)。在接下来的 $k-1$ 行中，每行输出两个整数 $u_i$ 和 $v_i$ ($1 \le u_i, v_i \le k$)，描述顶点 $u_i$ 和 $v_i$ 之间的边。输出的边必须构成一棵树。

如果存在多个解决方案，输出其中任意一个即可。你不需要最小化或最大化 $k$ 的值。

样例

样例输入 1

6
2 1 5 3 1 1

样例输出 1

0
5
1 2
2 3
1 4
1 5

说明 1

在给定的序列中，我们可以删除数字 $5$，并将剩余数字的顺序改为 $3, 2, 1, 1, 1$。在输出中，我们看到第一行为 $x = 0$（我们没有修改任何值），接下来的行描述了一棵具有 $k = 5$ 个顶点的树。输出的树的度数与上述完全一致。

样例输入 2

3
1 2 2

样例输出 2

1
3
1 2
2 3

说明 2

这一次，仅删除元素是不够的。我们可以将序列 $1, 2, 2$ 修改为 $1, 2, 1$，这使得 $x = 1$。这是最优解（最小可能的修改次数 $x$）。

子任务

在某些测试组中（至少一组），不需要修改任何元素，即在最优解中 $x = 0$。

测试

由于本题的特殊性，评测组决定在本题中禁止在论坛上分享测试数据。但在“文件”板块中，可以找到评测组准备的一些测试数据包。