F. Бинарный поиск с одним обменом
ограничение по времени на тест
1.5 секунд
ограничение по памяти на тест
512 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

Рассмотрим следующий алгоритм поиска числа $$$x$$$ в массиве $$$a$$$ длины $$$n$$$, элементы которого пронумерованы от $$$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$$$ рассмотреть все пары $$$(i, j)$$$, для которых $$$1 \le i \lt j \le n$$$. Для каждой из этих пар необходимо вычислить ее красоту — количество целых чисел $$$x$$$ от $$$1$$$ до $$$n$$$, которые могут быть успешно найдены описанным алгоритмом, если взять массив $$$a = [1, 2, 3, \dots, n]$$$ и поменять местами элементы $$$a_i$$$ и $$$a_j$$$. После этого для каждого $$$k$$$ от $$$0$$$ до $$$n$$$ необходимо вывести $$$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$$$.