On vous donne une permutation $p$ de longueur $n$. Pour un sous-segment continu de $p$, on définit son coût comme la longueur de la plus longue sous-suite strictement croissante de ce sous-segment. Pour une partition de $p$ en sous-segments disjoints, on définit son coût comme la somme des coûts de ces sous-segments.

On définit $a_k$ comme le coût maximal parmi les partitions de $p$ en $k$ sous-segments disjoints non vides.

Vous devez trouver $a_k$ pour chaque $k$ de $1$ à $n$.

Entrée

L'entrée contient plusieurs cas de test. La première ligne contient un seul entier $t$ ($1 \le t \le 10^3$), le nombre de cas de test. La description des cas de test suit.

La première ligne de chaque cas de test contient un entier $n$ ($1 \le n \le 10^5$).

La deuxième ligne contient $n$ entiers distincts $p_1, p_2, \dots, p_n$ ($1 \le p_i \le n$). Ensemble, ils définissent une permutation de $1, 2, \dots, n$.

La somme de $n$ sur l'ensemble des cas de test ne dépasse pas $10^5$.

Sortie

Pour chaque cas de test, affichez $a_1, a_2, \dots, a_n$ sur une seule ligne.

Exemples

Entrée 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

Sortie 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

Remarque

Considérons le troisième cas de test avec la permutation $p = [2, 4, 1, 3, 6, 5, 8, 7]$ :

• Pour $k = 1$, la réponse est simplement la longueur de la plus longue sous-suite croissante dans $p$, soit $a_1 = 4$.
• Pour $k = 2$, la partition en $[2, 4]$ et $[1, 3, 6, 5, 8, 7]$ a le coût maximal : $a_2 = 2 + 4 = 6$.
• Pour $k = 3$, la partition en $[2, 4]$, $[1, 3, 6]$ et $[5, 8, 7]$ a le coût maximal : $a_3 = 2 + 3 + 2 = 7$.
• Pour $k = 4$, la partition en $[2, 4]$, $[1, 3, 6]$, $[5, 8]$ et $[7]$ a le coût maximal : $a_4 = 2 + 3 + 2 + 1 = 8$.
• Pour $k > 4$, il est facile de voir que $a_k = 8$.