Дана перестановка \(p\) длины \(n\).
Можно выбрать любую её подпоследовательность, удалить её из перестановки и приписать в начало перестановки в том же порядке.
Для каждого \(k\) от \(0\) до \(n\) найдите минимальное количество инверсий в перестановке, которое можно получить, выбрав подпоследовательность длины ровно \(k\).
Выходные данные
Для каждого набора выведите \(n + 1\) число, где \(i\)-е число — ответ на задачу для длины подпоследовательности, равной \(i - 1\).
Примечание
Во втором наборе:
- Для длины \(0\): \([4, 2, 1, 3] \rightarrow [4, 2, 1, 3]\): \(4\) инверсии.
- Для длины \(1\): \([4, 2, \mathbf{1}, 3] \rightarrow [1, 4, 2, 3]\): \(2\) инверсии.
- Для длины \(2\): \([4, \mathbf{2}, \mathbf{1}, 3] \rightarrow [2, 1, 4, 3]\) или \([4, 2, \mathbf{1}, \textbf{3}] \rightarrow [1, 3, 4, 2]\): \(2\) инверсии.
- Для длины \(3\): \([4, \mathbf{2}, \mathbf{1}, \mathbf{3}] \rightarrow [2, 1, 3, 4]\): \(1\) инверсия.
- Для длины \(4\): \([\mathbf{4}, \mathbf{2}, \mathbf{1}, \mathbf{3}] \rightarrow [4, 2, 1, 3]\): \(4\) инверсии.
Примеры
| № | Входные данные | Выходные данные |
|
1
|
3
1
1
4
4 2 1 3
5
5 1 3 2 4
|
0 0
4 2 2 1 4
5 4 2 2 1 5
|