Вам дана одна перестановка $p$ длины $n$. Для непрерывного подотрезка перестановки $p$ определим его стоимость как длину наибольшей возрастающей подпоследовательности этого подотрезка. Для разбиения перестановки $p$ на непересекающиеся подотрезки определим его стоимость как сумму стоимостей этих подотрезков.

Определим $a_k$ как максимальную стоимость среди всех разбиений перестановки $p$ на $k$ непустых непересекающихся подотрезков.

Вам необходимо найти $a_k$ для каждого $k$ от $1$ до $n$.

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

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

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

Вторая строка содержит $n$ различных целых чисел $p_1, p_2, \dots, p_n$ ($1 \le p_i \le n$). Вместе они задают перестановку чисел $1, 2, \dots, n$.

Сумма $n$ по всем наборам входных данных не превосходит $10^5$.

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

Для каждого набора входных данных выведите $a_1, a_2, \dots, a_n$ в одной строке.

Примеры

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

5
5
1 2 3 4 5
5
5 4 3 2 1
8
2 4 1 3 6 5 8 7
9
3 2 1 6 5 4 9 8 7
1
1

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

5 5 5 5 5
1 2 3 4 5
4 6 7 8 8 8 8 8
3 4 5 6 7 8 9 9 9
1

Примечание

Рассмотрим третий набор входных данных с перестановкой $p = [2, 4, 1, 3, 6, 5, 8, 7]$:

• При $k = 1$ ответом является просто длина наибольшей возрастающей подпоследовательности в $p$, то есть $a_1 = 4$.
• При $k = 2$ разбиение на $[2, 4]$ и $[1, 3, 6, 5, 8, 7]$ имеет максимальную стоимость: $a_2 = 2 + 4 = 6$.
• При $k = 3$ разбиение на $[2, 4]$, $[1, 3, 6]$ и $[5, 8, 7]$ имеет максимальную стоимость: $a_3 = 2 + 3 + 2 = 7$.
• При $k = 4$ разбиение на $[2, 4]$, $[1, 3, 6]$, $[5, 8]$ и $[7]$ имеет максимальную стоимость: $a_4 = 2 + 3 + 2 + 1 = 8$.
• При $k > 4$ легко видеть, что $a_k = 8$.