Вам дано одну перестановку $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$.