题目描述

给定带权完全图 $G = (V, E)$，其中 $V = \{1, 2, \ldots, n\}$，边 $(i, j)$ 的权值为 $\lvert i - j \rvert$，求 $G$ 的最大生成仙人掌的边权和，并给出一组构造。

输入格式

共一行，包含一个正整数 $n$，表示仙人掌的点数。

输出格式

第一行包含一个整数，表示最大边权和。

第二行包含一个非负整数 $k$，表示你给出的仙人掌的边数。

接下来 $k$ 行，每行输出两个正整数 $u, v$ 表示仙人掌的一条边。

注意：如果对于所有的测试点，输出的第一行正确，可以获得 $\color{red} 33 \%$ 的分数。但是如果你只要这个部分分，你也要在后面输出一个合法的仙人掌 (但不需要满足你的答案)。

4

8
4
1 3
1 4
2 3
2 4

数据范围与提示

对于所有的测试点，保证 $1 \leq n \leq 5 \times 10^5$。