Gegeben ist eine Permutation $p$ der Länge $n$. Für ein zusammenhängendes Teilsegment von $p$ definieren wir seine Kosten als die Länge der längsten aufsteigenden Teilfolge dieses Teilsegments. Für eine Zerlegung von $p$ in disjunkte Teilsegmente definieren wir ihre Kosten als die Summe der Kosten dieser Teilsegmente.

Definiere $a_k$ als die maximalen Kosten unter allen Zerlegungen von $p$ in $k$ nicht-leere disjunkte Teilsegmente.

Du musst $a_k$ für jedes $k$ von $1$ bis $n$ bestimmen.

Eingabe

Die Eingabe enthält mehrere Testfälle. Die erste Zeile enthält eine einzelne ganze Zahl $t$ ($1 \le t \le 10^3$), die Anzahl der Testfälle. Es folgt die Beschreibung der Testfälle.

Die erste Zeile jedes Testfalls enthält eine ganze Zahl $n$ ($1 \le n \le 10^5$).

Die zweite Zeile enthält $n$ verschiedene ganze Zahlen $p_1, p_2, \dots, p_n$ ($1 \le p_i \le n$). Zusammen definieren sie eine Permutation von $1, 2, \dots, n$.

Die Summe von $n$ über alle Testfälle hinweg überschreitet $10^5$ nicht.

Ausgabe

Gib für jeden Testfall $a_1, a_2, \dots, a_n$ in einer Zeile aus.

Beispiele

Eingabe 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

Ausgabe 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

Hinweis

Betrachte den dritten Testfall mit der Permutation $p = [2, 4, 1, 3, 6, 5, 8, 7]$:

• Für $k = 1$ ist die Antwort einfach die Länge der längsten aufsteigenden Teilfolge in $p$, also $a_1 = 4$.
• Für $k = 2$ hat die Zerlegung in $[2, 4]$ und $[1, 3, 6, 5, 8, 7]$ die maximalen Kosten: $a_2 = 2 + 4 = 6$.
• Für $k = 3$ hat die Zerlegung in $[2, 4]$, $[1, 3, 6]$ und $[5, 8, 7]$ die maximalen Kosten: $a_3 = 2 + 3 + 2 = 7$.
• Für $k = 4$ hat die Zerlegung in $[2, 4]$, $[1, 3, 6]$, $[5, 8]$ und $[7]$ die maximalen Kosten: $a_4 = 2 + 3 + 2 + 1 = 8$.
• Für $k > 4$ ist leicht zu sehen, dass $a_k = 8$ gilt.