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

Just A Grid 城市（简称 JAG 城市）有 $N$ 条水平道路和 $N$ 条竖直道路。这些道路构成一个正方形网格。任意两条相邻的平行道路之间的距离均为 $1$。水平道路从上到下编号为 $1$ 到 $N$，竖直道路从左到右编号为 $1$ 到 $N$。我们将第 $i$ 条水平道路与第 $j$ 条竖直道路的交点记为 $(i,j)$。 JAG 城市的道路上即将举行一场马拉松。为了让跑者经过城市中的更多地方，组织者设置了 $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$ 次。 路线**允许自交**，即使交叉发生在路线不转弯的交点处也可以。每次转弯时，路线从水平道路转入竖直道路，或从竖直道路转入水平道路。 若一条路线满足上述所有条件，则称其为合法路线。保证至少存在一条合法路线。在所有合法路线中，输出一条长度**最大**的路线。  *图 E-1：合法与不合法的马拉松路线示例。图中从左到右的标签分别表示“合法但非最优”“最优”“不合法”“不合法”；Checkpoint 表示检查点。* 图 E-1 展示了样例输入对应的四条路线。最左边的路线合法但非最优，长度为 $12$。第二条路线最优，长度为 $14$。虽然它在两个不转弯的交点处自交，但这样的交叉是允许的。第三条路线不合法，因为它经过了一个检查点，却没有在那里转弯。最右边的路线不合法，因为它的转弯次数超过了 $2N$。

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

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