Se te da una permutación $p$ de longitud $n$. Para un subsegmento continuo de $p$, se define su costo como la longitud de la subsecuencia creciente más larga de este subsegmento. Para una partición de $p$ en subsegmentos disjuntos, se define su costo como la suma de los costos de estos subsegmentos.

Define $a_k$ como el costo máximo entre las particiones de $p$ en $k$ subsegmentos disjuntos no vacíos.

Debes encontrar $a_k$ para cada $k$ desde $1$ hasta $n$.

Entrada

La entrada contiene varios casos de prueba. La primera línea contiene un único entero $t$ ($1 \le t \le 10^3$), el número de casos de prueba. A continuación sigue la descripción de los casos de prueba.

La primera línea de cada caso de prueba contiene un entero $n$ ($1 \le n \le 10^5$).

La segunda línea contiene $n$ enteros diferentes $p_1, p_2, \dots, p_n$ ($1 \le p_i \le n$). Juntos, definen una permutación de $1, 2, \dots, n$.

La suma de $n$ en todos los casos de prueba no supera $10^5$.

Salida

Para cada caso de prueba, imprime $a_1, a_2, \dots, a_n$ en una línea.

Ejemplos

Entrada 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

Salida 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

Nota

Consideremos el tercer caso de prueba con la permutación $p = [2, 4, 1, 3, 6, 5, 8, 7]$:

• Para $k = 1$, la respuesta es simplemente la longitud de la subsecuencia creciente más larga en $p$, que es $a_1 = 4$.
• Para $k = 2$, la partición en $[2, 4]$ y $[1, 3, 6, 5, 8, 7]$ tiene el costo máximo: $a_2 = 2 + 4 = 6$.
• Para $k = 3$, la partición en $[2, 4]$, $[1, 3, 6]$ y $[5, 8, 7]$ tiene el costo máximo: $a_3 = 2 + 3 + 2 = 7$.
• Para $k = 4$, la partición en $[2, 4]$, $[1, 3, 6]$, $[5, 8]$ y $[7]$ tiene el costo máximo: $a_4 = 2 + 3 + 2 + 1 = 8$.
• Para $k > 4$, es fácil ver que $a_k = 8$.