CF2203F.Binary Search with One Swap

Consider the following algorithm for searching for an integer $x$ in an array $a$ of length $n$, where the elements are numbered from $1$ to $n$:

1. initialize $l = 1$ and $r = n$;
2. if $l \gt r$, terminate the algorithm and report that the desired element was not found;
3. compute $m = \lfloor \frac{l + r}{2} \rfloor$;
4. if $a_m = x$, terminate the algorithm and report that the desired element was found;
5. if $a_m \lt x$, set $l = m + 1$, otherwise set $r = m - 1$;
6. go to step $2$.

It can be shown that if the array $a$ is sorted in non-decreasing order, then any element of $a$ will be successfully found by this algorithm.

Your task is as follows: for a given number $n$, consider all pairs $(i, j)$ such that $1 \le i \lt j \le n$. For each of these pairs, you need to calculate its beauty — the number of integers $x$ from $1$ to $n$ that can be successfully found by the described algorithm if we take the array $a = [1, 2, 3, \dots, n]$ and swap the elements $a_i$ and $a_j$. After that, for each $k$ from $0$ to $n$, you need to output $p_k$ — the number of pairs with beauty $k$.

考虑以下在长度为 $n$ 的数组 $a$ 中搜索整数 $x$ 的算法，其中数组元素编号从 $1$ 到 $n$：

1. 初始化 $l = 1$ 和 $r = n$；
2. 若 $l \gt r$，则终止算法，并报告目标元素未找到；
3. 计算 $m = \lfloor \frac{l + r}{2} \rfloor$；
4. 若 $a_m = x$，则终止算法，并报告目标元素已找到；
5. 若 $a_m \lt x$，则令 $l = m + 1$；否则令 $r = m - 1$；
6. 返回第 $2$ 步。

可以证明：若数组 $a$ 按非递减顺序排序，则该算法总能成功找到 $a$ 中的任意元素。

你的任务如下：给定一个正整数 $n$，考虑所有满足 $1 \le i \lt j \le n$ 的数对 $(i, j)$。对每个这样的数对，你需要计算其“美观度”（beauty）——即：当取初始数组 $a = [1, 2, 3, \dots, n]$ 并交换其中第 $i$ 个与第 $j$ 个元素后，该算法能够成功找到的、属于区间 $[1, n]$ 的整数 $x$ 的个数。随后，对每个 $k$（从 $0$ 到 $n$），输出 $p_k$ —— 即美观度恰好为 $k$ 的数对的个数。

The only line of the input contains one integer $n$ ($3 \le n \le 5 \cdot 10^6$).

输入仅包含一行，其中有一个整数 $n$（$3 \le n \le 5 \cdot 10^6$）。

Print $n+1$ integers $p_0, p_1, \dots, p_n$, where $p_k$ is the number of pairs $(i, j)$ with beauty $k$.

输出 $n+1$ 个整数 $p_0, p_1, \dots, p_n$，其中 $p_k$ 表示美丽值为 $k$ 的数对 $(i, j)$ 的个数。

Consider an example where $n = 4$:

• if we swap $a_1$ and $a_2$, then $1$, $3$, and $4$ can be successfully found;
• if we swap $a_1$ and $a_3$, then $2$ and $4$ can be successfully found;
• if we swap $a_2$ and $a_3$, then $1$, $3$, and $4$ can be successfully found;
• if we swap $a_1$ and $a_4$, then $2$ and $3$ can be successfully found;
• if we swap $a_2$ and $a_4$, then $1$ and $4$ can be successfully found;
• if we swap $a_3$ and $a_4$, then $1$, $2$, and $4$ can be successfully found.

考虑一个 $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$。