P17530 [JAG 2026 Summer Camp #1] JAG City Marathon I

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. - 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. The course **may 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. It is guaranteed that at least one valid route exists. Among all valid routes, output one with the **maximum** possible length.  *Figure E-1: Examples of valid and invalid marathon courses* Figure E-1 shows four routes for the sample input. The leftmost route is valid but not optimal; its length is $12$. The second route is optimal, with length $14$. Although it crosses itself at two intersections where it does not turn, such crossings are allowed. The third route is invalid because it passes through a checkpoint without turning there. The rightmost route is invalid because it has more than $2N$ turns.

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\le 2\times 10^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 the permutation $P$.

Let $L$ be the maximum possible length of a valid route. Output $L$ and the $2N$ intersections at which a valid route of length $L$ turns, in the order in which they are visited along the course, in the following format: ```text L X_1 Y_1 X_2 Y_2 ... X_{2N} Y_{2N} ``` For each $i$ ($1\le i\le 2N$), 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 of length $L$, 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.