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

Just A Grid City（简称 JAG City）有 $N$ 条水平道路和 $N$ 条竖直道路。这些道路构成一个正方形网格。任意两条相邻的平行道路之间的距离为 $1$。水平道路从上到下编号为 $1$ 到 $N$，竖直道路从左到右编号为 $1$ 到 $N$。我们将第 $i$ 条水平道路与第 $j$ 条竖直道路的交点称为 $(i,j)$。 JAG City 将在这些道路上举办一场马拉松。为了让跑者经过城市中的许多地方，组织者设置了 $N$ 个检查点。给定 $(1,2,\ldots,N)$ 的一个排列 $P=(P_1,P_2,\ldots,P_N)$，检查点位于 $(i,P_i)$（$i=1,2,\ldots,N$）。 组织者希望赛道易于遵循。因此，马拉松赛道必须满足以下全部条件： - 赛道是一条只沿道路行进的闭合路线。仅在出发和结束时经过起点，其他任意点均不能经过超过一次。 - 赛道使用全部 $N$ 条水平道路和全部 $N$ 条竖直道路，且沿每条道路行进的距离至少为 $1$。 - 赛道经过每个检查点，且**在每个检查点都转弯**。 - 赛道恰好转弯 $2N$ 次。 特别地，赛道**不能自交**，即使是在不转弯的道路交点处也不行。每次转弯时，赛道都会从水平道路转入竖直道路，或从竖直道路转入水平道路。 满足上述全部条件的路线称为合法路线。  *图 I-1：合法与不合法的马拉松赛道示例。图中 Checkpoint 表示检查点，Valid 表示合法，Invalid 表示不合法。* 图 I-1 展示了样例输入对应的合法与不合法路线。最左侧的路线满足全部条件，因此合法。第二条路线发生自交，因此不合法。第三条路线的转弯次数超过 $2N$，因此不合法。最右侧的路线没有在每个检查点都转弯，因此不合法。 请输出一条满足全部条件的马拉松赛道。保证在给定约束下存在这样的赛道。 注意，你**不需要最大化或最小化**赛道的总长度。

输入包含一组测试数据，格式如下。 ```text N P_1 P_2 ... P_N ``` 第一行包含一个整数 $N$（$2\le N\le2\times10^5$），表示每个方向上的道路数量。 第二行包含 $N$ 个互不相同的整数 $P_1,P_2,\ldots,P_N$（$1\le P_i\le N$），它们组成排列 $P$。

按照沿赛道经过的顺序，输出赛道转弯的 $2N$ 个道路交点，格式如下： ```text X_1 Y_1 X_2 Y_2 ... X_{2N} Y_{2N} ``` 对于每个 $i$（$1\le i\le2N$），$(X_i,Y_i)$ 表示第 $X_i$ 条水平道路与第 $Y_i$ 条竖直道路的交点，其中 $1\le X_i,Y_i\le N$。 如果存在多条合法路线，输出任意一条即可。 你可以选择任意一个转弯交点作为 $(X_1,Y_1)$，并沿赛道的任意一个方向输出这些交点。