为您提供一个包含 $$$n$$$ 行和 $$$n$$$ 列的板,编号从 $$$1$$$ 到 $$$n$$$。第 $$$a$$$ 行和第 $$$b$$$ 列的交集由 $$$(a, b)$$$ 表示。
半皇后攻击同一行、同一列和一条对角线上的单元格。更正式地说,如果 $$$a=c$$$ 或 $$$b=d$$$ 或 $$$a-b=c-d$$$,$$$(a, b)$$$ 上的半皇后会攻击单元 $$$(c, d)$$$。
蓝色细胞受到攻击。
构建最优解决方案。
输入
第一行包含一个整数 $$$n$$$ ($$$1 \le n \le 10^5$$$) — 棋盘的大小。
输出
在第一行中打印一个整数 $$$k$$$ — 半皇后的最小数量。
在接下来的 $$$k$$$ 行中,打印两个整数 $$$a_i$$$, $$$b_i$$$ ($$$1 \le a_i, b_i \le n$$$) — 第 $$$i$$$ 半皇后的位置。
如果有多个解决方案,请打印其中一个。
示例
输入 #1
1
输出 #1
1 1 1
输入 #2
2
输出 #2
1 1 1
输入 #3
3
输出 #3
2 1 1 1 2
注意
示例$$$1$$$:一个半皇后就足够了。注意:$$$(1, 1)$$$ 上的半皇后会攻击 $$$(1, 1)$$$。
示例$$$2$$$:一个半皇后也足够了。 $$$(1, 2)$$$ 或 $$$(2, 1)$$$ 将是错误的解决方案,因为 $$$(1, 2)$$$ 上的半皇后不会攻击单元格 $$$(2, 1)$$$,反之亦然。 $$$(2, 2)$$$ 也是一个有效的解决方案。
示例$$$3$$$:不可能用一个半皇后覆盖棋盘。 $$$2$$$ 半皇后有多种解决方案;您可以打印其中任何一个。