P17580 [JAG 2026 Summer Camp #3] JAG City Marathon II

Just A Grid City (JAG City) has $N$ horizontal roads and $N$ vertical roads. These roads form a square grid. The distance between any two neighboring parallel roads is $1$. The horizontal roads are numbered from $1$ to $N$ from top to bottom, and the vertical roads are numbered from $1$ to $N$ from left to right. We call the intersection of horizontal road $i$ and vertical road $j$ $(i,j)$. A marathon will be held on the roads of JAG City. To make the runners visit many parts of the city, the organizers have placed $N$ checkpoints. You are given a permutation $P=(P_1,P_2,\ldots,P_N)$ of $(1,2,\ldots,N)$. The checkpoints are placed at $(i,P_i)$ ($i=1,2,\ldots,N$). The organizers want the course to be easy to follow. Therefore, the marathon course must satisfy all of the following conditions: - The course is a closed route that uses only the roads, visits its starting point only at the start and at the end, and does not visit any other point more than once. - The course uses all $N$ horizontal roads and all $N$ vertical roads, traveling a distance of at least $1$ along every road. - The course passes through every checkpoint and **turns at every checkpoint**. - The course has exactly $2N$ turns. In particular, the course **must not cross itself**, even at intersections where it does not turn. At each turn, the course switches from a horizontal road to a vertical road or vice versa. A route is valid if it satisfies all the conditions above.  *Figure I-1: Examples of valid and invalid marathon courses.* Figure I-1 shows examples of valid and invalid routes for the sample input. The leftmost route is valid because it satisfies all the conditions. The second route is invalid because it crosses itself. The third route is invalid because it has more than $2N$ turns. The rightmost route is invalid because it does not turn at every checkpoint. Output one marathon course that satisfies all the conditions. It is guaranteed that such a course exists under the given constraints. Note that you **do not need to maximize or minimize** the total length of the course.

The input consists of a single test case of the following format. ```text N P_1 P_2 ... P_N ``` The first line contains an integer $N$ ($2\le N\le2\times10^5$), representing the number of roads in each direction. The second line contains $N$ distinct integers $P_1,P_2,\ldots,P_N$ ($1\le P_i\le N$), which form a permutation $P$.

Output the $2N$ intersections at which the course turns, in the order in which they are visited along the course, in the following format: ```text X_1 Y_1 X_2 Y_2 ... X_{2N} Y_{2N} ``` For each $i$ ($1\le i\le2N$), the pair $(X_i,Y_i)$ represents the intersection of horizontal road $X_i$ and vertical road $Y_i$, where $1\le X_i,Y_i\le N$. If there are multiple valid routes, you may output any of them. You may choose any turning intersection as $(X_1,Y_1)$ and output the intersections in either direction along the course.