F. Последовательные перестановки
ограничение по времени на тест
2 секунды
ограничение по памяти на тест
1024 мегабайта
ввод
стандартный ввод
вывод
стандартный вывод

Вам дана перестановка $$$a_1,a_2,\ldots,a_n$$$ первых $$$n$$$ натуральных чисел. Подмассив $$$[l,r]$$$ называется последовательным, если его можно переупорядочить так, чтобы он стал последовательностью последовательных целых чисел, или, более формально, если $$$$$$\max(a_l,a_{l+1},\ldots,a_r)-\min(a_l,a_{l+1},\ldots,a_r)=r-l$$$$$$ Для каждого $$$k$$$ в диапазоне $$$[0,n]$$$ выведите максимальное количество последовательных подмассивов массива $$$a$$$ среди всех способов перестановки последних $$$n-k$$$ элементов массива $$$a$$$.

Входные данные

Каждый тест содержит несколько наборов входных данных. Первая строка содержит количество наборов входных данных $$$t$$$ ($$$1 \le t \le 10^4$$$). Далее следует их описание.

Первая строка каждого набора входных данных содержит одно целое число $$$n$$$ ($$$1\le n\le 2\cdot 10^5$$$).

Вторая строка каждого набора входных данных содержит $$$n$$$ целых чисел $$$a_1, a_2, \ldots, a_n$$$ ($$$1 \le a_i \le n$$$). Гарантируется, что заданные числа образуют перестановку длины $$$n$$$.

Гарантируется, что сумма $$$n$$$ по всем наборам входных данных не превосходит $$$2\cdot 10^5$$$.

Выходные данные

Для каждого набора входных данных выведите $$$n+1$$$ целое число в качестве ответов для каждого $$$k$$$ в диапазоне $$$[0,n]$$$.

Пример
Входные данные
5
5
5 2 1 4 3
4
2 1 4 3
1
1
8
7 5 8 1 4 2 6 3
10
1 4 5 3 7 8 9 2 10 6
Выходные данные
15 15 11 10 9 9 
10 8 8 7 7 
1 1 
36 30 25 19 15 13 12 9 9 
55 55 41 35 35 25 22 22 19 17 17
Примечание

В первом наборе входных данных перестановки ответов для каждого $$$k$$$: $$$[1,2,3,4,5]$$$, $$$[5,4,3,2,1]$$$, $$$[5,2,3,4,1]$$$, $$$[5,2,1,3,4]$$$, $$$[5,2,1,4,3]$$$, $$$[5,2,1,4,3]$$$.

Во втором наборе входных данных перестановки ответов для каждого $$$k$$$: $$$[1,2,3,4]$$$, $$$[2,1,3,4]$$$, $$$[2,1,3,4]$$$ , $$$[2,1,4,3]$$$, $$$[2,1,4,3]$$$.