Alice 的朋友是“肾上腺素飙升”（Adrenaline Rush）赛车比赛的忠实粉丝，总是努力参加每一场比赛。然而这一次，轮到 Alice 来观看比赛了。为了确保她的朋友不会错过任何重要的细节，Alice 决定记录赛道上发生的一切。

Alice 在比赛开始前注意到的第一件事是赛车的编号。所有的赛车都按特定的顺序排在起跑线前。最靠近起跑线的车编号为 1，第二辆车编号为 2，以此类推，直到最后一辆车，编号为 $n$。Alice 心想：真方便！

比赛在倒计时中开始：“三！二！一！走！”。Alice 观察到赛车最初按其原始顺序出发。然而，随着比赛的进行，它们的顺序发生了变化。她记录下每一辆车超越另一辆车的情况，这本质上是它们在赛道上交换了位置。

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

比赛结束时，Alice 仔细记录下了赛车的最终顺序 $c_1, c_2, \dots, c_n$，其中 $c_1$ 代表比赛的获胜者。

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

输入格式

第一行包含一个整数 $n$ ($1 \le n \le 1000$)，表示比赛中的赛车数量。 第二行包含一个排列 $c_1, c_2, \dots, c_n$ ($1 \le c_i \le n, c_i \neq c_j$)，表示赛车的最终顺序。

输出格式

第一行应包含一个整数 $m$，表示比赛中可能发生的最大超越次数。 接下来的 $m$ 行，每行包含两个整数 $x$ 和 $y$ ($1 \le x, y \le n, x \neq y$)，表示一次超越事件，即赛车 $x$ 超越了赛车 $y$。这意味着赛车 $x$ 原本直接位于赛车 $y$ 之后，并超越了它。超越必须按照它们发生的顺序排列。

在所有 $m$ 次超越发生后，赛车必须以 $c_1, c_2, \dots, c_n$ 的顺序到达终点线。注意，任何赛车 $x$ 不得超越另一辆赛车 $y$ 超过一次。

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

样例

样例输入 1

3
2 3 1

样例输出 1

4
2 1
3 1
3 2
2 3

样例输入 2

1
1

样例输出 2

0

样例输入 3

2
1 2

样例输出 3

2
2 1
1 2