← 返回题目列表

Codeforces · 2052/A

A. 肾上腺素激增

中文机器翻译题面 查看原题

Alice 的朋友是 Adrenaline Rush 赛车比赛的忠实粉丝,并且总是努力参加每场比赛。然而,这一次,爱丽丝是观看比赛的人。为了确保她的朋友不会错过任何重要细节,爱丽丝决定记录赛道上发生的一切。

比赛开始前,爱丽丝注意到的第一件事是赛车的编号。所有赛车按照特定顺序排列在起跑线前。最靠近线路的汽车编号为 $$$1$$$,第二辆车的编号为 $$$2$$$,依此类推,直到最后一辆车的编号为 $$$n$$$。多么方便啊! ——爱丽丝心想。

比赛以倒计时开始:“三!二!一!开始!”。爱丽丝观察到汽车按照原来的顺序启动。然而,随着比赛的进行,他们的顺序会发生变化。每当一辆车超越另一辆车时,她都会记录下来,本质上是在赛道上与它交换位置。

在比赛中,爱丽丝注意到一些奇怪的事情:没有一辆车超过另一辆车超过一次。换句话说,对于任意两辆车 $$$x$$$ 和 $$$y$$$,在比赛期间它们之间最多有两次超越:“$$$x$$$ 超越 $$$y$$$” 和/或“$$$y$$$ 超越 $$$x$$$”。

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

然而,Alice 的朋友只对最终排名感兴趣,并丢弃了 Alice 的除最终排序之外的所有笔记。 Alice 很好奇,她想知道: 她在比赛中观察到的最长可能的超车序列是多少? 你的任务是帮助 Alice 回答这个问题。

输入

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

第二行包含排列 $$$c_1, c_2, \ldots, c_n\;(1 \le c_i \le n, c_i \ne c_j)$$$ — 汽车的最终顺序。

输出

输出的第一行应包含一个整数 $$$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