考虑以下算法,用于在长度为 $$$n$$$ 的数组 $$$a$$$ 中搜索整数 $$$x$$$,其中元素编号从 $$$1$$$ 到 $$$n$$$:
- 初始化 $$$l = 1$$$ 和 $$$r = n$$$;
- 如果$$$l \gt r$$$,则终止算法并报告未找到所需元素;
- 计算 $$$m = \lfloor \frac{l + r}{2} \rfloor$$$;
- 如果$$$a_m = x$$$,则终止算法并报告找到所需元素;
- 如果$$$a_m \lt x$$$,则设置$$$l = m + 1$$$,否则设置$$$r = m - 1$$$;
- 转到步骤 $$$2$$$。
可以看出,如果数组$$$a$$$按非降序排序,则该算法将成功找到$$$a$$$中的任何元素。
你的任务如下:对于给定的数字$$$n$$$,考虑所有对$$$(i, j)$$$,使得$$$1 \le i \lt j \le n$$$。对于每一对,您需要计算其 美女 长度为 $$$m$$$(其中 $$$m \ge 2$$$)的数组 $$$b$$$ 的 — 如果我们采用数组 $$$a = [1, 2, 3, \dots, n]$$$ 并交换元素 $$$a_i$$$ 和 $$$a_j$$$ ,则通过所描述的算法可以成功找到的整数 $$$x$$$ 的数量。之后,对于从 $$$0$$$ 到 $$$n$$$ 的每个 $$$k$$$,您需要输出 $$$p_k$$$ — 与美丽 $$$k$$$ 配对的数量。
输入
输入的唯一一行包含一个整数 $$$n$$$ ($$$3 \le n \le 5 \cdot 10^6$$$)。
输出
打印 $$$n+1$$$ 整数 $$$p_0, p_1, \dots, p_n$$$,其中 $$$p_k$$$ 是 $$$(i, j)$$$ 与美丽 $$$k$$$ 的对数。
示例
输入复制
4
输出复制
0 0 3 3 0
输入复制
5
输出复制
0 0 2 4 4 0
输入复制
3
输出复制
0 1 2 0
输入复制
13
输出复制
0 0 0 0 0 0 1 3 8 9 21 24 12 0
注意
考虑一个 $$$n = 4$$$ 的示例:
- 如果我们交换$$$a_1$$$和$$$a_2$$$,则可以成功找到$$$1$$$、$$$3$$$和$$$4$$$;
- 如果我们交换$$$a_1$$$和$$$a_3$$$,则可以成功找到$$$2$$$和$$$4$$$;
- 如果我们交换$$$a_2$$$和$$$a_3$$$,则可以成功找到$$$1$$$、$$$3$$$和$$$4$$$;
- 如果我们交换$$$a_1$$$和$$$a_4$$$,则可以成功找到$$$2$$$和$$$3$$$;
- 如果我们交换$$$a_2$$$和$$$a_4$$$,则可以成功找到$$$1$$$和$$$4$$$;
- 如果我们交换$$$a_3$$$和$$$a_4$$$,则可以成功找到$$$1$$$、$$$2$$$和$$$4$$$。