给你一个长度为 $n$ 的排列 $p$。对于 $p$ 的一个连续子段，定义其代价为该子段的最长上升子序列的长度。对于将 $p$ 划分成若干不相交连续子段的一个划分，定义其代价为这些子段的代价之和。

定义 $a_k$ 为将 $p$ 划分成 $k$ 个非空不相交连续子段的所有划分中的最大代价。

你需要对每个从 $1$ 到 $n$ 的 $k$ 求出 $a_k$。

输入格式

输入包含多个测试用例。第一行包含一个整数 $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$。