题目描述

Ion 有一摞包含 $N$ 个元素的栈。现在他想把这些元素重新排成：从栈底到栈顶严格递增。

为了完成排序，他可以购买 $M$ 个额外的辅助栈，并执行 $K$ 次操作。一次操作为：

• 从某个栈的栈顶取出一个元素；
• 将它放到另一个栈的栈顶。

Ion 可以自行选择 $M$ 和 $K$。你需要输出一组操作，使得最后所有元素都回到初始栈中，并按从栈底到栈顶递增排列；同时评分会根据 $M\times K$ 的大小决定。

任务

输出一组使用 $M$ 个辅助栈、共 $K$ 次操作的方案，将初始栈排序。

输入格式

第一行一个整数 $N$。

第二行给出一个 $1\sim N$ 的排列，表示初始栈中从栈底到栈顶的元素顺序。也就是说，排列中的最后一个元素在栈顶。

输出格式

第一行输出两个整数 $M,K$。

接下来 $K$ 行，每行输出两个整数 $s,t$，表示将栈 $s$ 的栈顶元素移动到栈 $t$ 的栈顶。

初始栈编号为 $0$，购买的辅助栈编号为 $1,2,\ldots,M$。

为了获得分数，执行完所有操作后，栈 $0$ 必须包含全部 $N$ 个元素，并且从栈底到栈顶递增。

数据范围与评分

测试数据分为两类：

• 对于部分测试，$N=980$；
• 对于其余测试，$N=10000$。

当 $N=980$ 时：

• 若 $M\times K\le 60000$，获得该测试点 100% 分数；
• 若 $60000<M\times K\le 200000$，获得该测试点 60% 分数；
• 若 $200000<M\times K\le 3000000$，获得该测试点 20% 分数。

当 $N=10000$ 时：

• 若 $M\times K\le 800000$，获得该测试点 100% 分数；
• 若 $800000<M\times K\le 6000000$，获得该测试点 60% 分数；
• 若 $6000000<M\times K\le 300000000$，获得该测试点 20% 分数。

样例

输入

3
3 2 1

一种可行输出

2 9
0 1
0 1
0 1
1 2
1 2
1 2
2 0
2 0
2 0

样例解释

购买 2 个辅助栈。前三次操作把初始栈中的元素移到栈 1；接下来三次把栈 1 中的元素移到栈 2；最后三次把元素移回栈 0，得到有序栈。