← 返回题目列表

Codeforces · 53/D

D. 体育

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

Vasya 是一名学校体育老师。与其他体育老师不同,瓦西亚不喜欢学生按照身高排队。相反,他要求孩子们按照以下顺序站立:a1,a2,...,an,其中 ai 是队列中第 i 个学生的身高,n 是队列中学生的数量。孩子们很难记住这种奇怪的排列,今天他们按照以下顺序排成一排:b1,b2,……,bn,这让瓦夏非常不高兴。现在 Vasya 想要重新排列子级,使结果顺序如下:a1, a2, ..., an。在每次移动过程中,瓦夏可以交换队列中相邻的两个人。帮助 Vasya,找到导致 Vasya 需要的排列的交换顺序。不需要最小化移动次数。

输入

第一行包含一个整数 n (1 ≤ n ≤ 300),它是学生的数量。第二行包含n个空格分隔的整数ai (1 ≤ ai ≤ 109),表示占据第i位的学生必须拥有的身高。第三行包含n个空格分隔的整数bi (1 ≤ bi ≤ 109),表示初始排列中占据第i位的学生的身高。有些学生可能具有相似的身高。保证可以按所需的顺序排列子项,即 a 和 b 作为多重集重合。

输出

在第一行打印一个整数 k (0 ≤ k ≤ 106),它是移动次数。不需要最小化 k,但不能超过 106。然后打印 k 行,每行包含两个空格分隔的整数。第 pi, pi + 1 (1 ≤ pi ≤ n - 1) 行表示 Vasya 应该交换占据 pi 和 pi + 1 位置的学生。

示例

输入 #1

4
1 2 3 2
3 2 1 2

输出 #1

4
2 3
1 2
3 4
2 3

输入 #2

2
1 100500
1 100500

输出 #2

0