給定一個長度為 $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$。