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 $ .

The only line of the input contains one integer $ 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 $ .

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.