長さ $n$ の 1 つの順列 $p$ が与えられます。$p$ の連続する部分区間について、そのコストをその部分区間の最長増加部分列の長さと定義します。$p$ を互いに素な連続部分区間へ分割したものについて、そのコストをそれらの部分区間のコストの総和と定義します。

$p$ を $k$ 個の空でない互いに素な連続部分区間へ分割する方法全体における最大のコストを $a_k$ と定義します。

$1$ から $n$ までの各 $k$ について $a_k$ を求めてください。

入力

入力は複数のテストケースを含みます。1 行目にはテストケースの個数を表す 1 つの整数 $t$（$1 \le t \le 10^3$）が与えられます。続いて各テストケースの記述が与えられます。

各テストケースの 1 行目には整数 $n$（$1 \le n \le 10^5$）が与えられます。

2 行目には $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 行に出力してください。

入出力例

入力 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]$ が与えられる 3 番目のテストケースを考えます：

• $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$ であることが容易にわかります。