New Online Judge 主页 问题 来源/分类 竞赛&作业 状态 排名 常见问答
登录 注册

2149: 重新排版

内存限制：256 MB 时间限制：1 S 标准输入输出
题目类型：传统 评测方式：Special Judge 上传者：
提交：2 通过：1
提交提交记录统计

题目描述

给定一本有 n 页的原版书籍，现在需要对书籍重新排版。
对于给定排列 a，a[i] 表示原版第 i 页内容需要放到新版的第 a[i] 页。
对于每次排版需要对原版书籍和新版书籍进行翻页操作。
例如当前处于原版书籍第 12 页，新版书籍第 3 页。
接下来需要将原版第 5 页的内容复制到新版的第 8 页，则需要进行 |12-5|+|3-8|=12 次翻页。
现在两本书籍都处于第 1 页，你需要找一种顺序复制所有页面，同时保证翻页次数不超过 $2n\sqrt{n}$（向上取整）。

输入格式

第一行为正整数 n，1≤n≤10000。
第二行为 n 个整数，表示排列 a。1≤a[i]≤n，a[i] 互不相同。

输出格式

按顺序输出 n 对数字表示复制的顺序，每对数字 <i,j> 表示原版第 i 页复制到新版第 j 页。
输出任意一组解即可，要求翻页次数不超过 2n根号n。

输入样例 复制 

样例1：
3
2 1 3

样例2：
5
4 1 3 5 2

输出样例 复制 

样例1：
2 1
1 2
3 3

样例2：
2 1
3 3
5 2
4 5
1 4

数据范围与提示

来源：2022.BAPC