畀你一個長度為 $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$。