Annettuna on yksi pituutta $n$ oleva permutaatio $p$. Permutaation $p$ yhtenäiselle osavälille määritellään sen hinta kyseisen osavälin pisimmän kasvavan osajonon pituudeksi. Permutaation $p$ ositukselle erillisiksi osaväleiksi määritellään sen hinta näiden osavälien hintojen summaksi.

Määritellään $a_k$ suurimmaksi hinnaksi kaikkien sellaisten ositusten joukossa, joissa $p$ jaetaan $k$ epätyhjäksi erilliseksi osaväliksi.

Sinun tulee etsiä $a_k$ jokaiselle $k$ luvusta $1$ lukuun $n$.

Syöte

Syöte sisältää useita testitapauksia. Ensimmäisellä rivillä on yksi kokonaisluku $t$ ($1 \le t \le 10^3$), testitapausten lukumäärä. Seuraavaksi esitetään testitapausten kuvaukset.

Jokaisen testitapauksen ensimmäisellä rivillä on kokonaisluku $n$ ($1 \le n \le 10^5$).

Toisella rivillä on $n$ eri kokonaislukua $p_1, p_2, \dots, p_n$ ($1 \le p_i \le n$). Yhdessä ne määrittelevät lukujen $1, 2, \dots, n$ permutaation.

Lukujen $n$ summa yli kaikkien testitapausten ei ylitä lukua $10^5$.

Tuloste

Tulosta jokaiselle testitapaukselle luvut $a_1, a_2, \dots, a_n$ yhdelle riville.

Esimerkit

Syöte 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

Tuloste 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

Huomautus

Tarkastellaan kolmatta testitapausta, jossa permutaatio on $p = [2, 4, 1, 3, 6, 5, 8, 7]$:

• Kun $k = 1$, vastaus on yksinkertaisesti permutaation $p$ pisimmän kasvavan osajonon pituus, joka on $a_1 = 4$.
• Kun $k = 2$, ositus osaväleihin $[2, 4]$ ja $[1, 3, 6, 5, 8, 7]$ antaa suurimman hinnan: $a_2 = 2 + 4 = 6$.
• Kun $k = 3$, ositus osaväleihin $[2, 4]$, $[1, 3, 6]$ ja $[5, 8, 7]$ antaa suurimman hinnan: $a_3 = 2 + 3 + 2 = 7$.
• Kun $k = 4$, ositus osaväleihin $[2, 4]$, $[1, 3, 6]$, $[5, 8]$ ja $[7]$ antaa suurimman hinnan: $a_4 = 2 + 3 + 2 + 1 = 8$.
• Kun $k > 4$, on helppo nähdä, että $a_k = 8$.