Gefin er ein umröðun $p$ af lengd $n$. Fyrir samfellt hlutbil í $p$ skilgreinum við kostnað þess sem lengd lengstu vaxandi hlutrunu þessa hlutbils. Fyrir skiptingu á $p$ í sundurlæg hlutbil skilgreinum við kostnað hennar sem summu kostnaða þessara hlutbila.

Skilgreinum $a_k$ sem hámarkskostnaðinn meðal allra skiptinga á $p$ í $k$ ótóm sundurlæg hlutbil.

Þú þarft að finna $a_k$ fyrir hvert $k$ frá $1$ til $n$.

Inntak

Inntakið inniheldur nokkur prófunartilvik. Fyrsta línan inniheldur eina heiltölu $t$ ($1 \le t \le 10^3$), fjölda prófunartilvika. Lýsing á prófunartilvikunum fylgir.

Fyrsta línan í hverju prófunartilviki inniheldur heiltölu $n$ ($1 \le n \le 10^5$).

Önnur línan inniheldur $n$ ólíkar heiltölur $p_1, p_2, \dots, p_n$ ($1 \le p_i \le n$). Saman skilgreina þær umröðun á $1, 2, \dots, n$.

Summa $n$ yfir öll prófunartilvik fer ekki yfir $10^5$.

Úttak

Fyrir hvert prófunartilvik skaltu prenta $a_1, a_2, \dots, a_n$ á eina línu.

Dæmi

Inntak 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

Úttak 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

Athugasemd

Skoðum þriðja prófunartilvikið með umröðuninni $p = [2, 4, 1, 3, 6, 5, 8, 7]$:

• Fyrir $k = 1$ er svarið einfaldlega lengd lengstu vaxandi hlutrununnar í $p$, sem er $a_1 = 4$.
• Fyrir $k = 2$ hefur skiptingin í $[2, 4]$ og $[1, 3, 6, 5, 8, 7]$ hámarkskostnaðinn: $a_2 = 2 + 4 = 6$.
• Fyrir $k = 3$ hefur skiptingin í $[2, 4]$, $[1, 3, 6]$ og $[5, 8, 7]$ hámarkskostnaðinn: $a_3 = 2 + 3 + 2 = 7$.
• Fyrir $k = 4$ hefur skiptingin í $[2, 4]$, $[1, 3, 6]$, $[5, 8]$ og $[7]$ hámarkskostnaðinn: $a_4 = 2 + 3 + 2 + 1 = 8$.
• Fyrir $k > 4$ er auðvelt að sjá að $a_k = 8$.