Du får en permutation $p$ av längd $n$. För ett sammanhängande delsegment av $p$, definiera dess kostnad som längden av den längsta växande delföljden i detta delsegment. För en partition av $p$ i disjunkta delsegment, definiera dess kostnad som summan av kostnaderna för dessa delsegment.

Definiera $a_k$ som den maximala kostnaden bland alla partitioner av $p$ i $k$ icke-tomma disjunkta delsegment.

Du behöver hitta $a_k$ för varje $k$ från $1$ till $n$.

Indata

Indata innehåller flera testfall. Den första raden innehåller ett enda heltal $t$ ($1 \le t \le 10^3$), antalet testfall. Beskrivningen av testfallen följer.

Den första raden i varje testfall innehåller ett heltal $n$ ($1 \le n \le 10^5$).

Den andra raden innehåller $n$ olika heltal $p_1, p_2, \dots, p_n$ ($1 \le p_i \le n$). Tillsammans definierar de en permutation av $1, 2, \dots, n$.

Summan av $n$ över alla testfall överstiger inte $10^5$.

Utdata

För varje testfall, skriv ut $a_1, a_2, \dots, a_n$ på en rad.

Exempel

Indata 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

Förklaring

Betrakta det tredje testfallet med permutationen $p = [2, 4, 1, 3, 6, 5, 8, 7]$:

• För $k = 1$ är svaret helt enkelt längden av den längsta växande delföljden i $p$, vilket är $a_1 = 4$.
• För $k = 2$ har partitionen i $[2, 4]$ och $[1, 3, 6, 5, 8, 7]$ den maximala kostnaden: $a_2 = 2 + 4 = 6$.
• För $k = 3$ har partitionen i $[2, 4]$, $[1, 3, 6]$ och $[5, 8, 7]$ den maximala kostnaden: $a_3 = 2 + 3 + 2 = 7$.
• För $k = 4$ har partitionen i $[2, 4]$, $[1, 3, 6]$, $[5, 8]$ och $[7]$ den maximala kostnaden: $a_4 = 2 + 3 + 2 + 1 = 8$.
• För $k > 4$ är det lätt att se att $a_k = 8$.