CF1667C.Half Queen Cover

You are given a board with $n$ rows and $n$ columns, numbered from $1$ to $n$. The intersection of the $a$-th row and $b$-th column is denoted by $(a, b)$.

A half-queen attacks cells in the same row, same column, and on one diagonal. More formally, a half-queen on $(a, b)$ attacks the cell $(c, d)$ if $a=c$ or $b=d$ or $a-b=c-d$.

The blue cells are under attack.

What is the minimum number of half-queens that can be placed on that board so as to ensure that each square is attacked by at least one half-queen?

Construct an optimal solution.

你有一个 $n$ 行 $n$ 列的棋盘，行列编号均为 $1$ 到 $n$。第 $a$ 行与第 $b$ 列的交点记为 $(a, b)$。

一个“半后”（half-queen）可攻击其所在行、所在列以及其中一条对角线上的所有格子。更准确地说，位于 $(a, b)$ 的半后会攻击格子 $(c, d)$，当且仅当满足以下任一条件：$a=c$ 或 $b=d$ 或 $a-b=c-d$。

图中蓝色格子处于攻击范围内。

问：在该棋盘上至少需要放置多少个半后，才能保证每个格子都至少被一个半后攻击到？

请构造一种最优方案。

The first line contains a single integer $n$ ($1 \le n \le 10^5$) — the size of the board.

第一行包含一个整数 $n$（$1 \le n \le 10^5$）——棋盘的大小。

In the first line print a single integer $k$ — the minimum number of half-queens.

In each of the next $k$ lines print two integers $a_i$, $b_i$ ($1 \le a_i, b_i \le n$) — the position of the $i$-th half-queen.

If there are multiple solutions, print any.

第一行输出一个整数 $k$ —— 半皇后所需的最少数量。

接下来的 $k$ 行中，每行输出两个整数 $a_i$、$b_i$（$1 \le a_i, b_i \le n$）—— 第 $i$ 个半皇后的位置。

若存在多种解，输出任意一种即可。

Example $1$: one half-queen is enough. Note: a half-queen on $(1, 1)$ attacks $(1, 1)$.

Example $2$: one half-queen is enough too. $(1, 2)$ or $(2, 1)$ would be wrong solutions, because a half-queen on $(1, 2)$ does not attack the cell $(2, 1)$ and vice versa. $(2, 2)$ is also a valid solution.

Example $3$: it is impossible to cover the board with one half queen. There are multiple solutions for $2$ half-queens; you can print any of them.

示例 $1$：只需一个半皇后即可。注意：位于 $(1, 1)$ 的半皇后可以攻击 $(1, 1)$ 自身。

示例 $2$：同样只需一个半皇后即可。$(1, 2)$ 或 $(2, 1)$ 均为错误解，因为位于 $(1, 2)$ 的半皇后无法攻击格子 $(2, 1)$，反之亦然。$(2, 2)$ 也是一个合法解。

示例 $3$：无法仅用一个半皇后覆盖整个棋盘。使用 $2$ 个半皇后则存在多种可行方案；你可以输出其中任意一种。