25988번 - Inked Inscriptions 스페셜 저지다국어

문제

The year is 1337. You are a hardworking monk in your abbey, and today you have been tasked to make a copy of your abbey's psalm book. However, there is a problem. The old psalm book sorted psalms by age: each time a new psalm made its way into the abbey, it was added in the back. The head monk wants the new book to be sorted by title instead to make specific psalms easier to find. This means that you need to write all psalms on different pages in the new book! Since there can be a lot of psalms (each fitting on one page), this requires some careful planning.

To copy a psalm, both books need to be opened on the proper page. (Note that psalms are only written on the right-hand pages, and therefore, only the right-hand pages are numbered.) For example, suppose that you want to copy a psalm from page 5ドル$ of the old book to page 8ドル$ of the new book. Also suppose that the old book is currently opened on page 12ドル$ and the new book is opened on page 3ドル$. Then, you need to flip $|12-5| = 7$ pages in the old book and $|3-8| = 5$ pages of the new book to arrive at the proper pages. This takes 7ドル+5 = 12$ page flips in total. Since books are very fragile and valuable, you want to limit the number of page flips needed to copy all the psalms.

Both books are initially opened on page 1ドル$. In which order should you copy the psalms to ensure that you use at most 2ドルn\sqrt{n}$ page flips (rounded up)?

입력

The input consists of:

• One line with an integer $n$ (1ドル\leq n\leq 10^4$), the number of psalms.
• One line with a permutation of the integers 1ドル$ to $n$. If the $i$-th integer is $j,ドル then you should copy the psalm on page $i$ of the old book to page $j$ of the new book.

출력

Output $n$ pairs of integers, where each pair $i$ and $j$ indicates that the psalm on page $i$ of the old book should be copied to page $j$ of the new book.

Each psalm should be copied exactly once and onto the correct page. The total number of page flips needed to perform these instructions should be at most 2ドルn\sqrt{n},ドル rounded up.

If there are multiple valid solutions, you may output any one of them. The number of required page flips does not need to be minimal.

제한

힌트