Дана перестановка \(p\) длины \(n\).
Можно выбрать любую её подпоследовательность, удалить её из перестановки и приписать в начало перестановки в том же порядке.
Для каждого \(k\) от \(0\) до \(n\) найдите минимальное количество инверсий в перестановке, которое можно получить, выбрав подпоследовательность длины ровно \(k\).
В первой строке задано одно целое число \(t\) (\(1 \le t \le 50\,000\)) — количество наборов входных данных.
В первой строке каждого набора вводится число \(n\) (\(1 \le n \le 5 \cdot 10^5\)) — длина перестановки.
Во второй строке каждого набора вводится перестановка \(p_1, p_2, \ldots, p_n\) (\(1 \le p_i \le n\)).
Гарантируется, что сумма \(n\) не превосходит \(5 \cdot 10^5\).
Для каждого набора выведите \(n + 1\) число, где \(i\)-е число — ответ на задачу для длины подпоследовательности, равной \(i - 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
2000 ms 256 Mb Правила оформления программ и список ошибок при автоматической проверке задач