Задача №115160. Split sort
Изучив все известные алгоритмы сортировки Лёша решил придумать свой собственный. Новый алгоритм он называет «split-sort». Его идея заключается в том, чтобы несколько раз применить к сортируемому массиву длины \(n\) следующие три операции:
- Выбрать число \(k\) от \(1\) до \(n\).
- Удалить некоторые \(k\) элементов массива.
- Приписать удаленные элементы в начало массива в обратном порядке.
Например, для массива [5, 1, 4, 2, 3] можно выбрать \(k = 3\), удалить элементы \([1, 4, 3]\), после чего массив станет равным \([5, 2]\), а затем приписать удаленные в начало в обратном порядке, после чего массив станет равным \([3, 4, 1, 5, 2]\).
Леша всё ещё изучает свойства изобретенного алгоритма. Сейчас он пытается понять, как работа алгоритма зависит от выбора числа \(k\). А именно, для данной перестановки \(p\) чисел \(1, 2, \dots, n\) и для каждого \(k\) от \(1\) до \(n\) он хочет понять, какой минимальной неупорядоченности можно добиться, сделав одну операцию с данным \(k\).
Перестановкой \(p\) чисел \(1, 2, \dots n\) называется массив \([p_1, p_2, \dots p_n]\), такой что \(1 \le p_i \le n\) и \(p_i \neq p_j\) при \(i \neq j\)
Неупорядоченностью перестановки \(p\) Леша называет количество инверсий в ней, то есть количество таких пар \(i\), \(j\), что \(i < j\) и \(p_i > p_j\).
У Леши ещё очень много важных алгоритмов, которые он хочет обдумать, а потому изучение алгоритма «split-sort» он поручил вам, справитесь ли вы с такой задачей?
Первая строка содержит единственное целое число \(n\) \((1 \le n \le 300\,000)\) — длину перестановки.
Вторая строка содержит \(n\) целых чисел \(p_1, p_2, \ldots, p_n\) (\(1 \le p_i \le n, p_i \neq p_j\), если \(i \neq j\)) — элементы перестановки.
Выведите \(n\) чисел, где \(k\)-е число равно минимальной неупорядоченности перестановки, которой можно добиться применением одной описанной выше операции с \(k\) элементами.
В первом примере:
- При \(k = 1\): выбираем элемент \([1]\): \([5, 1, 4, 2, 3] \rightarrow [5, 4, 2, 3] \rightarrow [1, 5, 4, 2, 3]\) — \(5\) пар, расположенных в неправильном порядке.
- При \(k = 2\): выбираем элементы \([1, 2]\): \([5, 1, 4, 2, 3] \rightarrow [5, 4, 3] \rightarrow [2, 1, 5, 4, 3]\) — \(4\) пары, расположенные в неправильном порядке.
- При \(k = 3\): выбираем элементы \([1, 2, 3]\): \([5, 1, 4, 2, 3] \rightarrow [5, 4] \rightarrow [3, 2, 1, 5, 4]\) — \(4\) пары, расположенные в неправильном порядке.
- При \(k = 4\): выбираем элементы \([5, 1, 4, 2]\): \([5, 1, 4, 2, 3] \rightarrow [3] \rightarrow [2, 4, 1, 5, 3]\) — \(4\) пары, расположенные в неправильном порядке.
- При \(k = 5\): выбираем элементы \([5, 1, 4, 2, 3]\): \([5, 1, 4, 2, 3] \rightarrow [] \rightarrow [3, 2, 4, 1, 5]\) — \(4\) пары, расположенные в неправильном порядке.
5 5 1 4 2 3
5 4 4 4 4
5 1 2 3 4 5
0 1 3 6 10
5 3 5 1 2 4
3 2 2 3 5