题目背景

公元 1337 年，你是一座修道院里的抄写员，今天需要把旧诗篇集完整誊写到一本新书中。

旧书中的诗篇按进入修道院的时间排列，而新书需要按标题排序。因此，每一篇诗篇在两本书中的页码通常不同。抄写一篇诗篇时，两本书都必须翻到对应页；为了保护这些珍贵而脆弱的书籍，你希望控制总翻页次数。

题目描述

共有 $n$ 篇诗篇，每篇恰好占据一页。

给定一个 $1$ 到 $n$ 的排列 $p$。其中 $p_i=j$ 表示：旧书第 $i$ 页上的诗篇应当被抄写到新书第 $j$ 页。

两本书初始都打开在第 $1$ 页。

若当前旧书打开在第 $x$ 页、新书打开在第 $y$ 页，而下一篇要抄写的诗篇对应旧书第 $i$ 页和新书第 $j$ 页，则需要翻动

$$|x-i|+|y-j|$$

页。

你需要输出一种抄写顺序，使每篇诗篇恰好被抄写一次，并且总翻页次数不超过

$$\left\lceil 2n\sqrt n\right\rceil.$$

假设你的输出顺序依次为

$$(i_1,j_1),(i_2,j_2),\ldots,(i_n,j_n),$$

则总翻页次数为

$$|1-i_1|+|1-j_1| +\sum_{t=2}^{n}\left(|i_t-i_{t-1}|+|j_t-j_{t-1}|\right).$$

输入格式

第一行包含一个整数 $n$（$1\le n\le 10^4$），表示诗篇数量。

第二行包含一个 $1$ 到 $n$ 的排列 $p_1,p_2,\ldots,p_n$。其中 $p_i=j$ 表示旧书第 $i$ 页上的诗篇应抄写到新书第 $j$ 页。

输出格式

输出 $n$ 行，每行包含两个整数 $i$ 和 $j$，表示把旧书第 $i$ 页上的诗篇抄写到新书第 $j$ 页。

输出必须满足：

• 每个旧书页码 $i\in[1,n]$ 恰好出现一次；
• 对于每一行输出的 $(i,j)$，必须有 $j=p_i$；
• 按输出顺序执行全部操作时，总翻页次数不得超过 $\left\lceil 2n\sqrt n\right\rceil$。

若存在多种合法方案，输出任意一种即可。你不需要最小化总翻页次数。

样例 1

输入

3
2 1 3

输出

2 1
1 2
3 3

样例 2

输入

5
4 1 3 5 2

输出

2 1
3 3
5 2
4 5
1 4