Du får oppgitt én permutasjon $p$ av lengde $n$. For et sammenhengende delsegment av $p$, definer kostnaden som lengden på den lengste stigende delfølgen i dette delsegmentet. For en partisjon av $p$ i disjunkte delsegmenter, definer kostnaden som summen av kostnadene til disse delsegmentene.

Definer $a_k$ som den maksimale kostnaden blant alle partisjoner av $p$ i $k$ ikke-tomme disjunkte delsegmenter.

Du må finne $a_k$ for hver $k$ fra $1$ til $n$.

Inndata

Inndataene inneholder flere testtilfeller. Den første linjen inneholder et enkelt heltall $t$ ($1 \le t \le 10^3$), antallet testtilfeller. Beskrivelsen av testtilfellene følger.

Den første linjen i hvert testtilfelle inneholder et heltall $n$ ($1 \le n \le 10^5$).

Den andre linjen inneholder $n$ forskjellige heltall $p_1, p_2, \dots, p_n$ ($1 \le p_i \le n$). Sammen definerer de en permutasjon av $1, 2, \dots, n$.

Summen av $n$ over alle testtilfeller overstiger ikke $10^5$.

Utdata

For hvert testtilfelle, skriv ut $a_1, a_2, \dots, a_n$ på én linje.

Eksempler

Inndata 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

Utdata 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

Forklaring

Betrakt det tredje testtilfellet med permutasjonen $p = [2, 4, 1, 3, 6, 5, 8, 7]$:

• For $k = 1$ er svaret bare lengden på den lengste stigende delfølgen i $p$, som er $a_1 = 4$.
• For $k = 2$ har partisjonen i $[2, 4]$ og $[1, 3, 6, 5, 8, 7]$ maksimal kostnad: $a_2 = 2 + 4 = 6$.
• For $k = 3$ har partisjonen i $[2, 4]$, $[1, 3, 6]$ og $[5, 8, 7]$ maksimal kostnad: $a_3 = 2 + 3 + 2 = 7$.
• For $k = 4$ har partisjonen i $[2, 4]$, $[1, 3, 6]$, $[5, 8]$ og $[7]$ maksimal kostnad: $a_4 = 2 + 3 + 2 + 1 = 8$.
• For $k > 4$ er det lett å se at $a_k = 8$.