#P17530. [JAG 2026 Summer Camp #1] JAG City Marathon I
[JAG 2026 Summer Camp #1] JAG City Marathon I
Problem Description
Just A Grid City (JAG City) has horizontal roads and vertical roads. These roads form a square grid. The distance between any two neighboring parallel roads is . The horizontal roads are numbered from to from top to bottom, and the vertical roads are numbered from to from left to right. We call the intersection of horizontal road and vertical road .
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 checkpoints. You are given a permutation of . The checkpoints are placed at ().
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 horizontal roads and all vertical roads, traveling a distance of at least along every road.
- The course passes through every checkpoint and turns at every checkpoint.
- The course has exactly 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 . The second route is optimal, with length . 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 turns.
Input Format
The input consists of a single test case of the following format.
N
P_1 P_2 ... P_N
The first line contains an integer (), representing the number of roads in each direction.
The second line contains distinct integers (), which form the permutation .
Output Format
Let be the maximum possible length of a valid route.
Output and the intersections at which a valid route of length turns, in the order in which they are visited along the course, in the following format:
L
X_1 Y_1
X_2 Y_2
...
X_{2N} Y_{2N}
For each (), the pair represents the intersection of horizontal road and vertical road , where .
If there are multiple valid routes of length , you may output any of them.
You may choose any turning intersection as and output the intersections in either direction along the course.
4
2 4 1 3
14
1 2
1 3
4 3
4 1
3 1
3 4
2 4
2 2