Description

Alice 的朋友是《Adrenaline Rush》赛车比赛的忠实粉丝，总是尽力参加每一场比赛。然而，这一次，比赛是 Alice 观看的。为了确保她的朋友不会错过任何重要细节，Alice 决定记录比赛中赛道上发生的所有事情。

比赛开始前，Alice 首先注意到车子的编号。所有车子按特定顺序排在起跑线上，距离起跑线最近的车编号为 $1$，第二辆车编号为 $2$，以此类推，直到最后一辆车，编号为 $n$。这太方便了！——Alice 想。

比赛开始时，倒计时开始：“三！二！一！开始！” Alice 观察到，车子按照最初的顺序起跑。然而，随着比赛的进行，车子的顺序发生了变化。她记录下每次当一辆车超越另一辆车时，基本上是在赛道上交换了位置。

在比赛过程中，Alice 注意到一件有趣的事情：没有任何一辆车超越另一辆车超过一次。换句话说，对于任何两辆车 $x$ 和 $y$，它们之间最多发生两次超车：$x$ 超越 $y$ 或者 $y$ 超越 $x$。

比赛结束后，Alice 仔细写下了车子的最终顺序 $c_1, c_2, \ldots, c_n$，其中 $c_1$ 代表比赛的冠军。

然而，Alice 的朋友只对最终排名感兴趣，除了最终的顺序，其他记录都被丢弃。由于 Alice 很好奇，她想知道：她在比赛中可能观察到的最长超车序列是什么？你的任务是帮助 Alice 解答这个问题。

Input Format

第一行输入一个整数 $n\;(1 \le n \le 1000)$ —— 参赛车的数量。

第二行输入一个排列 $c_1, c_2, \ldots, c_n\;(1 \le c_i \le n, c_i \ne c_j)$ —— 车子最终的顺序。

Output Format

输出的第一行应包含一个整数 $m$ —— 比赛中可能发生的最大超车次数。

接下来的 $m$ 行每行应包含两个整数 $x$ 和 $y$ ($1 \le x, y \le n, x \ne y$)，表示一次超车事件，其中车 $x$ 超越了车 $y$。这意味着车 $x$ 原本在车 $y$ 后面并超越了它。超车事件必须按发生的顺序输出。

所有的 $m$ 次超车发生后，车子应当以 $c_1, c_2, \ldots, c_n$ 的顺序到达终点。注意，任何车 $x$ 不应当超越另一辆车 $y$ 超过一次。

如果存在多个可能的最长超车序列，输出其中任意一个。

3
2 3 1

4
2 1
3 1
3 2
2 3

1
1

0

2
1 2

2
2 1
1 2