十分好的不含杂质 Ad-Hoc 构造！难度：\(8/10\)，另外几道有难度然后这么好玩的构造题应该是 P12336 第三心脏（比这个题简单一点），P14025 [ICPC 2024 Nanjing R] P ⊕ Q = R（比这个题难一点）。P14158 [ICPC 2022 Nanjing R] 三角形 是史诗级大份，建议别做。
首先容易发现当 \(2\nmid n\) 的时候必然无解，因此只需要考虑 \(2\mid n\) 的情况即可。
\(n=2\) 的情况是简单的，直接对两个数做一次操作就全相等了。而扩展到 \(n=4\) 也不难，考虑把四个数分成两组 \((A,B)\) 和 \((C,D)\)，对两组的数分别执行一次操作得到 \(AB,AB,CD,CD\)，然后此时再交叉配对即 \(A,C\) 做一次操作 \(B,D\) 做一次操作就可以得到四个 \(ABCD\) 满足条件。
同理可以扩展到 \(n=2^k\)：先将序列分为两个长度为 \(\frac n2\) 的序列，对两个序列分别递归处理然后再合并，合并直接把 \(1,\frac n2+1\)，\(2,\frac n2+2\)，\(\ldots\)，\(\frac n2,n\) 分别配对处理即可。执行操作的次数是 \(T(n)=2T(\frac n2)+O(n)\) 用主定理计算可知操作次数是 \(O(n\log n)\) 级别的。
然后再考虑另外一种构造方案：从 \(n=k-2\) 来推导出 \(n=k\) 时的构造方案。对于给定的 \(n\)，先构造 \(n=2\) 时的答案，然后考虑一步一步扩展 \(+2\) 得到答案。首先把在最后加入的两个数做一次操作让这两个数的值相等，得到形如 \(a,a,a,\ldots,a,b,b\) 的序列。然后考虑下面的算法：
- 让前 \(n-4\) 个 \(a\) 依次和第一个 \(b\) 执行操作，得到序列 \(ab,a^2b,a^3b,\ldots,a^{n-4}b,a,a,a^{n-4}b,b\)。
- 对前 \(n-4\) 个数首尾匹配，即第 \(1\) 个数和第 \(n-4\) 个数做一次操作，第 \(2\) 个数和第 \(n-3\) 个数做一次操作，以此类推。此时前 \(n-4\) 个数的值都变为 \(a^{n-3}b^2\)。
- 对后 \(4\) 个数做操作，先让后两个数做一次操作得到两个 \(a^{n-4}b^2\)，然后再让第一个数和第三个数做一次操作，第二个数和第四个数做一次操作。此时这四个数的值都变为 \(a^{n-3}b^2\)。
- 于是此时整个序列的值都相等。
上述算法的执行操作次数是 \(T(n)=T(n-2)+O(n)\) 的，简单计算可知有 \(T(n)=O(n^2)\)。
但是这显然是不好的，考虑优化。每次只在序列末尾加两个数就需要扫一遍整个序列过于浪费。考虑沿用之前 \(n=2^k\) 时的处理思路，将长度为 \(n\) 的序列进行分治：
- 若 \(4\mid n\)，则直接将序列分为两个长度为 \(\frac n2\) 的序列然后按照 \(n=2^k\) 时的做法直接合并。
- 若 \(4\nmid n\)，则需要将序列分为一个长度为 \(\frac n2-1\) 和一个长度为 \(\frac n2+1\) 的序列，分别递归处理，然后将第一个序列和第二个序列除最后两个元素以外的部分进行合并，用前面提到的 \(n=k-2\) 推导 \(n=k\) 的构造方案处理最后剩下的两个元素。
上述算法的执行操作次数是 \(T(n)=2T(\frac n2)+O(n)\) 的，主定理计算可知操作次数是 \(O(n\log n)\) 级别的。到这里位置都是比较容易的。
但是上述算法仍然无法通过，观察题目信息可知最终需要的操作次数应该是 \(2n-1\) 才能通过该题。
思考为什么之前的算法可以以一个比较优的操作次数构造出答案。容易发现，上面的算法构造了一个次数形如等差数列的序列，这样一来只需要两两配对就可以使得其次数均相等。
于是考虑使用类似的思想，执行下面给出的算法：
- 对于一个长度为 \(n\)（\(2\mid n\)）的序列 \(a_1,a_2,\ldots,a_n\)，考虑将其先两两分组，将 \(a_{2k-1}\) 和 \(a_{2k}\) 分为一组然后执行一次操作让她们的值相等。此时得到的序列形如 \(p_1,p_1,p_2,p_2,\ldots,p_m,p_m\)（\(m=\frac n2\)）。
- 对 \(a_1\) 和 \(a_{n-2}\) 做一次操作，此时有 \(a_1=a_{n-2}=p_1p_{m-1}\)。
- 对 \(a_2\) 和 \(a_{n-3}\) 做一次操作，此时有 \(a_2=a_{n-3}=p_1p_{m-1}\)。
- 扫一遍所有的奇数位，依次执行操作 \((1,n-1),(3,n-1),(5,n-1),\ldots,(n-5,n-1)\)。
- 执行操作 \((2,n-1)\)。
- 逆序扫一遍所有的偶数位，执行操作 \((n-4,n-1),(n-2,n-1),\ldots,(4,n-1)\)。
- 此时得到的序列形如：
- 对于 \(a_1,a_3,a_5,\ldots,a_{n-5}\) 的值而言，有：\(a_{2i-1}=p_1p_{m-1}p_m\prod\limits_{j=2}^ip_j\)。
- 对于 \(a_4,a_6,a_8,\ldots,a_{n-4}\) 的值而言，有：\(a_{2i}=p_1^2p_{m-1}^2p_m(\prod\limits_{j=2}^{i-1}p_j)(\prod\limits_{j=i}^{m-2}p_j^2)\)。
- 特殊的，有 \(a_2=p_1^2p_{m-1}^2p_m\prod\limits_{j=2}^{m-2}p_j\)，\(a_{n-1}=p_1^2p_{m-1}^2p_m\prod\limits_{j=2}^{m-2}p_j^2\)。
- 对于剩下几个位置而言有：\(a_{n-3}=a_{n-2}=p_1p_{m-1},a_n=p_m\)。
- 然后沿用前面直接配对消出的套路，执行下面的操作：
- 对于任意的 \(i\in[1,m-3]\cap\mathbb{N_+}\)，都对 \((2i-1,2i+2)\) 执行一次操作。也就是对 \(a_1\) 和 \(a_4\)，\(a_3\) 和 \(a_6\)，\(a_5\) 和 \(a_8\)，……，\(a_{n-7}\) 和 \(a_{n-4}\) 执行一次操作。
- 特殊的， 还需要额外对 \(a_2,a_{n-5}\) 执行一次操作（注意上面的操作漏掉了对这两个位置的覆盖）
- 此时得到的序列（记原序列为 \(a\)，新得到的序列为 \(a’\)）形如：
- \(a'_1=a'_2=a'_3=\ldots=a'_{n-4}=a_1^3a_2^3a_{n-3}^3a_{n-2}^3a_{n-1}^2a_n^2a_3^2a_4^2a_5^2a_6^2\ldots a_{n-5}^2a_{n-4}^2\)。
- \(a'_{n-3}=a'_{n-2}=a_1a_2a_{n-3}a_{n-2}\)。
- \(a'_{n-1}=a_1^2a_2^2a_{n-3}^2a_{n-2}^2a_{n-1}a_na_3^2a_4^2a_5^2a_6^2\ldots a_{n-5}^2a_{n-4}^2\)。
- \(a’_n=a_{n-1}a_n\)。
- 即此时 \(a’\) 序列的前 \(n-4\) 项的值均相同，之后倒数第 \(3,4\) 项的值也是相同的。
- 最后对后 \(4\) 个位置执行操作，对 \((n-1,n)\)，\((n-3,n-1)\)，\((n-2,n)\) 三组位置执行操作。最终所有位置的值均为 \(a_1^3a_2^3a_{n-3}^3a_{n-2}^3a_{n-1}^2a_n^2a_3^2a_4^2a_5^2a_6^2\ldots a_{n-5}^2a_{n-4}^2\)，符合题目的要求。
经过简单计算可知上述算法共执行了 \(2n-1\) 次操作，符合题目给出的要求。
注意该算法需要特判 \(n=2,4,6\) 时的 corner case。
附：\(n=12\) 时上述算法执行的流程（\(a\) 序列的变化过程）
\[\begin{aligned}
(0);&(a_1,\ a_2,\ a_3,\ a_4,\ a_5,\ a_6,\ a_7,\ a_8,\ a_9,\ a_{10},\ a_{11},\ a_{12})\\
(1);&(a_1a_2,\ a_1a_2,\ a_3,\ a_4,\ a_5,\ a_6,\ a_7,\ a_8,\ a_9,\ a_{10},\ a_{11},\ a_{12})\\
(2);&(a_1a_2,\ a_1a_2,\ a_3a_4,\ a_3a_4,\ a_5,\ a_6,\ a_7,\ a_8,\ a_9,\ a_{10},\ a_{11},\ a_{12})\\
(3);&(a_1a_2,\ a_1a_2,\ a_3a_4,\ a_3a_4,\ a_5a_6,\ a_5a_6,\ a_7,\ a_8,\ a_9,\ a_{10},\ a_{11},\ a_{12})\\
(4);&(a_1a_2,\ a_1a_2,\ a_3a_4,\ a_3a_4,\ a_5a_6,\ a_5a_6,\ a_7a_8,\ a_7a_8,\ a_9,\ a_{10},\ a_{11},\ a_{12})\\
(5);&(a_1a_2,\ a_1a_2,\ a_3a_4,\ a_3a_4,\ a_5a_6,\ a_5a_6,\ a_7a_8,\ a_7a_8,\ a_9a_{10},\ a_9a_{10},\ a_{11},\ a_{12})\\
(6);&(a_1a_2,\ a_1a_2,\ a_3a_4,\ a_3a_4,\ a_5a_6,\ a_5a_6,\ a_7a_8,\ a_7a_8,\ a_9a_{10},\ a_9a_{10},\ a_{11}a_{12},\ a_{11}a_{12})\\
(7);&(a_1a_2a_9a_{10},\ a_1a_2,\ a_3a_4,\ a_3a_4,\ a_5a_6,\ a_5a_6,\ a_7a_8,\ a_7a_8,\ a_9a_{10},\ a_1a_2a_9a_{10},\ a_{11}a_{12},\ a_{11}a_{12})\\
(8);&(a_1a_2a_9a_{10},\ a_1a_2a_9a_{10},\ a_3a_4,\ a_3a_4,\ a_5a_6,\ a_5a_6,\ a_7a_8,\ a_7a_8,\ a_1a_2a_9a_{10},\ a_1a_2a_9a_{10},\ a_{11}a_{12},\ a_{11}a_{12})\\
(9);&(a_1a_2a_9a_{10}a_{11}a_{12},\ a_1a_2a_9a_{10},\ a_3a_4,\ a_3a_4,\ a_5a_6,\ a_5a_6,\ a_7a_8,\ a_7a_8,\ a_1a_2a_9a_{10},\ a_1a_2a_9a_{10},\ a_1a_2a_9a_{10}a_{11}a_{12},\ a_{11}a_{12})\\
(10);&(a_1a_2a_9a_{10}a_{11}a_{12},\ a_1a_2a_9a_{10},\ a_1a_2a_3a_4a_9a_{10}a_{11}a_{12},\ a_3a_4,\ a_5a_6,\ a_5a_6,\ a_7a_8,\ a_7a_8,\ a_1a_2a_9a_{10},\ a_1a_2a_9a_{10},\ a_1a_2a_3a_4a_9a_{10}a_{11}a_{12},\ a_{11}a_{12})\\
(11);&(a_1a_2a_9a_{10}a_{11}a_{12},\ a_1a_2a_9a_{10},\ a_1a_2a_3a_4a_9a_{10}a_{11}a_{12},\ a_3a_4,\ a_1a_2a_3a_4a_5a_6a_9a_{10}a_{11}a_{12},\ a_5a_6,\ a_7a_8,\ a_7a_8,\ a_1a_2a_9a_{10},\ a_1a_2a_9a_{10},\ a_1a_2a_3a_4a_5a_6a_9a_{10}a_{11}a_{12},\ a_{11}a_{12})\\
(12);&(a_1a_2a_9a_{10}a_{11}a_{12},\ a_1a_2a_9a_{10},\ a_1a_2a_3a_4a_9a_{10}a_{11}a_{12},\ a_3a_4,\ a_1a_2a_3a_4a_5a_6a_9a_{10}a_{11}a_{12},\ a_5a_6,\ a_1a_2a_3a_4a_5a_6a_7a_8a_9a_{10}a_{11}a_{12},\ a_7a_8,\ a_1a_2a_9a_{10},\ a_1a_2a_9a_{10},\ a_1a_2a_3a_4a_5a_6a_7a_8a_9a_{10}a_{11}a_{12},\ a_{11}a_{12})\\
(13);&(a_1a_2a_9a_{10}a_{11}a_{12},\ a_1^2a_2^2a_3a_4a_5a_6a_7a_8a_9^2a_{10}^2a_{11}a_{12},\ a_1a_2a_3a_4a_9a_{10}a_{11}a_{12},\ a_3a_4,\ a_1a_2a_3a_4a_5a_6a_9a_{10}a_{11}a_{12},\ a_5a_6,\ a_1a_2a_3a_4a_5a_6a_7a_8a_9a_{10}a_{11}a_{12},\ a_7a_8,\ a_1a_2a_9a_{10},\ a_1a_2a_9a_{10},\ a_1^2a_2^2a_3a_4a_5a_6a_7a_8a_9^2a_{10}^2a_{11}a_{12},\ a_{11}a_{12})\\
(14);&(a_1a_2a_9a_{10}a_{11}a_{12},\ a_1^2a_2^2a_3a_4a_5a_6a_7a_8a_9^2a_{10}^2a_{11}a_{12},\ a_1a_2a_3a_4a_9a_{10}a_{11}a_{12},\ a_3a_4,\ a_1a_2a_3a_4a_5a_6a_9a_{10}a_{11}a_{12},\ a_5a_6,\ a_1a_2a_3a_4a_5a_6a_7a_8a_9a_{10}a_{11}a_{12},\ a_1^2a_2^2a_3a_4a_5a_6a_7^2a_8^2a_9^2a_{10}^2a_{11}a_{12},\ a_1a_2a_9a_{10},\ a_1a_2a_9a_{10},\ a_1^2a_2^2a_3a_4a_5a_6a_7^2a_8^2a_9^2a_{10}^2a_{11}a_{12},\ a_{11}a_{12})\\
(15);&(a_1a_2a_9a_{10}a_{11}a_{12},\ a_1^2a_2^2a_3a_4a_5a_6a_7a_8a_9^2a_{10}^2a_{11}a_{12},\ a_1a_2a_3a_4a_9a_{10}a_{11}a_{12},\ a_3a_4,\ a_1a_2a_3a_4a_5a_6a_9a_{10}a_{11}a_{12},\ a_1^2a_2^2a_3a_4a_5^2a_6^2a_7^2a_8^2a_9^2a_{10}^2a_{11}a_{12},\ a_1a_2a_3a_4a_5a_6a_7a_8a_9a_{10}a_{11}a_{12},\ a_1^2a_2^2a_3a_4a_5a_6a_7^2a_8^2a_9^2a_{10}^2a_{11}a_{12},\ a_1a_2a_9a_{10},\ a_1a_2a_9a_{10},\ a_1^2a_2^2a_3a_4a_5^2a_6^2a_7^2a_8^2a_9^2a_{10}^2a_{11}a_{12},\ a_{11}a_{12})\\
(16);&(a_1a_2a_9a_{10}a_{11}a_{12},\ a_1^2a_2^2a_3a_4a_5a_6a_7a_8a_9^2a_{10}^2a_{11}a_{12},\ a_1a_2a_3a_4a_9a_{10}a_{11}a_{12},\ a_1^2a_2^2a_3^2a_4^2a_5^2a_6^2a_7^2a_8^2a_9^2a_{10}^2a_{11}a_{12},\ a_1a_2a_3a_4a_5a_6a_9a_{10}a_{11}a_{12},\ a_1^2a_2^2a_3a_4a_5^2a_6^2a_7^2a_8^2a_9^2a_{10}^2a_{11}a_{12},\ a_1a_2a_3a_4a_5a_6a_7a_8a_9a_{10}a_{11}a_{12},\ a_1^2a_2^2a_3a_4a_5a_6a_7^2a_8^2a_9^2a_{10}^2a_{11}a_{12},\ a_1a_2a_9a_{10},\ a_1a_2a_9a_{10},\ a_1^2a_2^2a_3^2a_4^2a_5^2a_6^2a_7^2a_8^2a_9^2a_{10}^2a_{11}a_{12},\ a_{11}a_{12})\\
(17);&(a_1^3a_2^3a_3^2a_4^2a_5^2a_6^2a_7^2a_8^2a_9^3a_{10}^3a_{11}^2a_{12}^2,\ a_1^2a_2^2a_3a_4a_5a_6a_7a_8a_9^2a_{10}^2a_{11}a_{12},\ a_1a_2a_3a_4a_9a_{10}a_{11}a_{12},\ a_1^3a_2^3a_3^2a_4^2a_5^2a_6^2a_7^2a_8^2a_9^3a_{10}^3a_{11}^2a_{12}^2,\ a_1a_2a_3a_4a_5a_6a_9a_{10}a_{11}a_{12},\ a_1^2a_2^2a_3a_4a_5^2a_6^2a_7^2a_8^2a_9^2a_{10}^2a_{11}a_{12},\ a_1a_2a_3a_4a_5a_6a_7a_8a_9a_{10}a_{11}a_{12},\ a_1^2a_2^2a_3a_4a_5a_6a_7^2a_8^2a_9^2a_{10}^2a_{11}a_{12},\ a_1a_2a_9a_{10},\ a_1a_2a_9a_{10},\ a_1^2a_2^2a_3^2a_4^2a_5^2a_6^2a_7^2a_8^2a_9^2a_{10}^2a_{11}a_{12},\ a_{11}a_{12})\\
(18);&(a_1^3a_2^3a_3^2a_4^2a_5^2a_6^2a_7^2a_8^2a_9^3a_{10}^3a_{11}^2a_{12}^2,\ a_1^2a_2^2a_3a_4a_5a_6a_7a_8a_9^2a_{10}^2a_{11}a_{12},\ a_1^3a_2^3a_3^2a_4^2a_5^2a_6^2a_7^2a_8^2a_9^3a_{10}^3a_{11}^2a_{12}^2,\ a_1^3a_2^3a_3^2a_4^2a_5^2a_6^2a_7^2a_8^2a_9^3a_{10}^3a_{11}^2a_{12}^2,\ a_1a_2a_3a_4a_5a_6a_9a_{10}a_{11}a_{12},\ a_1^3a_2^3a_3^2a_4^2a_5^2a_6^2a_7^2a_8^2a_9^3a_{10}^3a_{11}^2a_{12}^2,\ a_1a_2a_3a_4a_5a_6a_7a_8a_9a_{10}a_{11}a_{12},\ a_1^2a_2^2a_3a_4a_5a_6a_7^2a_8^2a_9^2a_{10}^2a_{11}a_{12},\ a_1a_2a_9a_{10},\ a_1a_2a_9a_{10},\ a_1^2a_2^2a_3^2a_4^2a_5^2a_6^2a_7^2a_8^2a_9^2a_{10}^2a_{11}a_{12},\ a_{11}a_{12})\\
(19);&(a_1^3a_2^3a_3^2a_4^2a_5^2a_6^2a_7^2a_8^2a_9^3a_{10}^3a_{11}^2a_{12}^2,\ a_1^2a_2^2a_3a_4a_5a_6a_7a_8a_9^2a_{10}^2a_{11}a_{12},\ a_1^3a_2^3a_3^2a_4^2a_5^2a_6^2a_7^2a_8^2a_9^3a_{10}^3a_{11}^2a_{12}^2,\ a_1^3a_2^3a_3^2a_4^2a_5^2a_6^2a_7^2a_8^2a_9^3a_{10}^3a_{11}^2a_{12}^2,\ a_1^3a_2^3a_3^2a_4^2a_5^2a_6^2a_7^2a_8^2a_9^3a_{10}^3a_{11}^2a_{12}^2,\ a_1^3a_2^3a_3^2a_4^2a_5^2a_6^2a_7^2a_8^2a_9^3a_{10}^3a_{11}^2a_{12}^2,\ a_1a_2a_3a_4a_5a_6a_7a_8a_9a_{10}a_{11}a_{12},\ a_1^3a_2^3a_3^2a_4^2a_5^2a_6^2a_7^2a_8^2a_9^3a_{10}^3a_{11}^2a_{12}^2,\ a_1a_2a_9a_{10},\ a_1a_2a_9a_{10},\ a_1^2a_2^2a_3^2a_4^2a_5^2a_6^2a_7^2a_8^2a_9^2a_{10}^2a_{11}a_{12},\ a_{11}a_{12})\\ (20);&(a_1^3a_2^3a_3^2a_4^2a_5^2a_6^2a_7^2a_8^2a_9^3a_{10}^3a_{11}^2a_{12}^2,\ a_1^3a_2^3a_3^2a_4^2a_5^2a_6^2a_7^2a_8^2a_9^3a_{10}^3a_{11}^2a_{12}^2,\ a_1^3a_2^3a_3^2a_4^2a_5^2a_6^2a_7^2a_8^2a_9^3a_{10}^3a_{11}^2a_{12}^2,\ a_1^3a_2^3a_3^2a_4^2a_5^2a_6^2a_7^2a_8^2a_9^3a_{10}^3a_{11}^2a_{12}^2,\ a_1^3a_2^3a_3^2a_4^2a_5^2a_6^2a_7^2a_8^2a_9^3a_{10}^3a_{11}^2a_{12}^2,\ a_1^3a_2^3a_3^2a_4^2a_5^2a_6^2a_7^2a_8^2a_9^3a_{10}^3a_{11}^2a_{12}^2,\ a_1^3a_2^3a_3^2a_4^2a_5^2a_6^2a_7^2a_8^2a_9^3a_{10}^3a_{11}^2a_{12}^2,\ a_1^3a_2^3a_3^2a_4^2a_5^2a_6^2a_7^2a_8^2a_9^3a_{10}^3a_{11}^2a_{12}^2,\ a_1a_2a_9a_{10},\ a_1a_2a_9a_{10},\ a_1^2a_2^2a_3^2a_4^2a_5^2a_6^2a_7^2a_8^2a_9^2a_{10}^2a_{11}a_{12},\ a_{11}a_{12})\\
(21);&(a_1^3a_2^3a_3^2a_4^2a_5^2a_6^2a_7^2a_8^2a_9^3a_{10}^3a_{11}^2a_{12}^2,\ a_1^3a_2^3a_3^2a_4^2a_5^2a_6^2a_7^2a_8^2a_9^3a_{10}^3a_{11}^2a_{12}^2,\ a_1^3a_2^3a_3^2a_4^2a_5^2a_6^2a_7^2a_8^2a_9^3a_{10}^3a_{11}^2a_{12}^2,\ a_1^3a_2^3a_3^2a_4^2a_5^2a_6^2a_7^2a_8^2a_9^3a_{10}^3a_{11}^2a_{12}^2,\ a_1^3a_2^3a_3^2a_4^2a_5^2a_6^2a_7^2a_8^2a_9^3a_{10}^3a_{11}^2a_{12}^2,\ a_1^3a_2^3a_3^2a_4^2a_5^2a_6^2a_7^2a_8^2a_9^3a_{10}^3a_{11}^2a_{12}^2,\ a_1^3a_2^3a_3^2a_4^2a_5^2a_6^2a_7^2a_8^2a_9^3a_{10}^3a_{11}^2a_{12}^2,\ a_1^3a_2^3a_3^2a_4^2a_5^2a_6^2a_7^2a_8^2a_9^3a_{10}^3a_{11}^2a_{12}^2,\ a_1a_2a_9a_{10},\ a_1a_2a_9a_{10},\ a_1^2a_2^2a_3^2a_4^2a_5^2a_6^2a_7^2a_8^2a_9^2a_{10}^2a_{11}^2a_{12}^2,\ a_1^2a_2^2a_3^2a_4^2a_5^2a_6^2a_7^2a_8^2a_9^2a_{10}^2a_{11}^2a_{12}^2)\\
(22);&(a_1^3a_2^3a_3^2a_4^2a_5^2a_6^2a_7^2a_8^2a_9^3a_{10}^3a_{11}^2a_{12}^2,\ a_1^3a_2^3a_3^2a_4^2a_5^2a_6^2a_7^2a_8^2a_9^3a_{10}^3a_{11}^2a_{12}^2,\ a_1^3a_2^3a_3^2a_4^2a_5^2a_6^2a_7^2a_8^2a_9^3a_{10}^3a_{11}^2a_{12}^2,\ a_1^3a_2^3a_3^2a_4^2a_5^2a_6^2a_7^2a_8^2a_9^3a_{10}^3a_{11}^2a_{12}^2,\ a_1^3a_2^3a_3^2a_4^2a_5^2a_6^2a_7^2a_8^2a_9^3a_{10}^3a_{11}^2a_{12}^2,\ a_1^3a_2^3a_3^2a_4^2a_5^2a_6^2a_7^2a_8^2a_9^3a_{10}^3a_{11}^2a_{12}^2,\ a_1^3a_2^3a_3^2a_4^2a_5^2a_6^2a_7^2a_8^2a_9^3a_{10}^3a_{11}^2a_{12}^2,\ a_1^3a_2^3a_3^2a_4^2a_5^2a_6^2a_7^2a_8^2a_9^3a_{10}^3a_{11}^2a_{12}^2,\ a_1^3a_2^3a_3^2a_4^2a_5^2a_6^2a_7^2a_8^2a_9^3a_{10}^3a_{11}^2a_{12}^2,\ a_1a_2a_9a_{10},\ a_1^3a_2^3a_3^2a_4^2a_5^2a_6^2a_7^2a_8^2a_9^3a_{10}^3a_{11}^2a_{12}^2,\ a_1^2a_2^2a_3^2a_4^2a_5^2a_6^2a_7^2a_8^2a_9^2a_{10}^2a_{11}^2a_{12}^2)\\
(23);&(a_1^3a_2^3a_3^2a_4^2a_5^2a_6^2a_7^2a_8^2a_9^3a_{10}^3a_{11}^2a_{12}^2,\ a_1^3a_2^3a_3^2a_4^2a_5^2a_6^2a_7^2a_8^2a_9^3a_{10}^3a_{11}^2a_{12}^2,\ a_1^3a_2^3a_3^2a_4^2a_5^2a_6^2a_7^2a_8^2a_9^3a_{10}^3a_{11}^2a_{12}^2,\ a_1^3a_2^3a_3^2a_4^2a_5^2a_6^2a_7^2a_8^2a_9^3a_{10}^3a_{11}^2a_{12}^2,\ a_1^3a_2^3a_3^2a_4^2a_5^2a_6^2a_7^2a_8^2a_9^3a_{10}^3a_{11}^2a_{12}^2,\ a_1^3a_2^3a_3^2a_4^2a_5^2a_6^2a_7^2a_8^2a_9^3a_{10}^3a_{11}^2a_{12}^2,\ a_1^3a_2^3a_3^2a_4^2a_5^2a_6^2a_7^2a_8^2a_9^3a_{10}^3a_{11}^2a_{12}^2,\ a_1^3a_2^3a_3^2a_4^2a_5^2a_6^2a_7^2a_8^2a_9^3a_{10}^3a_{11}^2a_{12}^2,\ a_1^3a_2^3a_3^2a_4^2a_5^2a_6^2a_7^2a_8^2a_9^3a_{10}^3a_{11}^2a_{12}^2,\ a_1^3a_2^3a_3^2a_4^2a_5^2a_6^2a_7^2a_8^2a_9^3a_{10}^3a_{11}^2a_{12}^2,\ a_1^3a_2^3a_3^2a_4^2a_5^2a_6^2a_7^2a_8^2a_9^3a_{10}^3a_{11}^2a_{12}^2,\ a_1^3a_2^3a_3^2a_4^2a_5^2a_6^2a_7^2a_8^2a_9^3a_{10}^3a_{11}^2a_{12}^2)
\end{aligned}
\]
namespace Loyalty
{int a[N];inline void init() {}inline void main([[maybe_unused]] int _ca, [[maybe_unused]] int _atc){int n;cin >> n;if (n & 1)cout << 0 << '\n';else if (n == 2)cout << 1 << '\n' << 1 << '\n' << 1 << ' ' << 2 << '\n';else if (n == 4){cout << 1 << '\n';cout << 4 << '\n';cout << 1 << ' ' << 2 << '\n';cout << 3 << ' ' << 4 << '\n';cout << 1 << ' ' << 3 << '\n';cout << 2 << ' ' << 4 << '\n';}else if (n == 6){cout << 1 << '\n';cout << 11 << '\n';cout << 1 << ' ' << 2 << '\n'; // 1cout << 3 << ' ' << 4 << '\n'; // 2cout << 1 << ' ' << 3 << '\n'; // 3cout << 2 << ' ' << 4 << '\n'; // 4cout << 5 << ' ' << 6 << '\n'; // 5cout << 1 << ' ' << 5 << '\n'; // 6cout << 2 << ' ' << 5 << '\n'; // 7cout << 1 << ' ' << 2 << '\n'; // 8cout << 5 << ' ' << 6 << '\n'; // 9cout << 3 << ' ' << 5 << '\n'; // 10cout << 4 << ' ' << 6 << '\n'; // 11}else{cout << 1 << '\n';vector<pair<int, int>> op;for (int i = 1; i <= n; i += 2)op.emplace_back(i, i + 1);op.emplace_back(1, n - 2);op.emplace_back(2, n - 3);for (int i = 1; i <= n - 5; i += 2)op.emplace_back(i, n - 1);op.emplace_back(2, n - 1);for (int i = n - 4; i >= 4; i -= 2)op.emplace_back(i, n - 1);for (int i = 1; i <= n / 2 - 3; ++i)op.emplace_back(2 * i - 1, 2 * i + 2);op.emplace_back(2, n - 5);op.emplace_back(n - 1, n);op.emplace_back(n - 3, n - 1);op.emplace_back(n - 2, n);cout << op.size() << '\n';for (auto &[x, y] : op)cout << x << ' ' << y << '\n';}}
}