数据节点容量统计

题目描述

某大型数据管理系统采用一种特殊的编号规则管理数据节点。

系统中共有 n 个节点，编号从 1 到 n。

对于编号为 i 的节点，定义：

节点容量 = i & (-i)

即：

capacity(i) = i & (-i)

其中：

• & 表示按位与运算；
• -i 表示整数 i 的相反数。

例如，节点编号为 12，其二进制表示为：

1100

而 -12 在计算机中使用补码表示，参与按位与运算时，最低位对应部分为：

0100

因此：

1100
& 0100
= 0100

所以编号为 12 的节点容量为 4。

现在需要对所有节点进行分析。请完成以下任务：

1. 输出每个节点的编号以及对应容量；
2. 找出所有节点中的最大容量；
3. 统计每一种容量出现的次数。

输入格式

输入一个整数 n，表示节点数量。

输出格式

第一部分：

输出 n 行，每行包含两个整数：

节点编号 容量

表示每个节点的编号和对应容量。

第二部分：

输出一个空行后，再输出一行：

max 最大容量

表示所有节点容量中的最大值。

第三部分：

再输出一个空行后，按照容量从小到大的顺序，输出所有出现过的容量及其出现次数。

每行包含两个整数：

容量 出现次数

输入样例 1

2

输出样例 1

1 1
2 2

max 2

1 1
2 1

输入样例 2

7

输出样例 2

1 1
2 2
3 1
4 4
5 1
6 2
7 1

max 4

1 4
2 2
4 1

数据范围

1 ≤ n ≤ 100000