Anda diberikan satu permutasi $p$ dengan panjang $n$. Untuk suatu subsegmen kontigu dari $p$, definisikan biayanya sebagai panjang upabarisan naik terpanjang (longest increasing subsequence) dari subsegmen ini. Untuk suatu partisi dari $p$ menjadi subsegmen-subsegmen yang saling lepas, definisikan biayanya sebagai jumlah dari biaya subsegmen-subsegmen tersebut.

Definisikan $a_k$ sebagai biaya maksimum di antara partisi-partisi dari $p$ menjadi $k$ subsegmen tak kosong yang saling lepas.

Anda perlu mencari $a_k$ untuk setiap $k$ dari $1$ hingga $n$.

Masukan

Masukan berisi beberapa kasus uji. Baris pertama berisi satu bilangan bulat $t$ ($1 \le t \le 10^3$), banyaknya kasus uji. Deskripsi dari masing-masing kasus uji menyusul.

Baris pertama dari setiap kasus uji berisi sebuah bilangan bulat $n$ ($1 \le n \le 10^5$).

Baris kedua berisi $n$ bilangan bulat berbeda $p_1, p_2, \dots, p_n$ ($1 \le p_i \le n$). Secara keseluruhan, bilangan-bilangan tersebut membentuk sebuah permutasi dari $1, 2, \dots, n$.

Jumlah nilai $n$ di seluruh kasus uji tidak melebihi $10^5$.

Keluaran

Untuk setiap kasus uji, cetaklah $a_1, a_2, \dots, a_n$ dalam satu baris.

Contoh

Masukan 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

Keluaran 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

Catatan

Perhatikan kasus uji ketiga dengan permutasi $p = [2, 4, 1, 3, 6, 5, 8, 7]$:

• Untuk $k = 1$, jawabannya hanyalah panjang upabarisan naik terpanjang di $p$, yaitu $a_1 = 4$.
• Untuk $k = 2$, partisi menjadi $[2, 4]$ dan $[1, 3, 6, 5, 8, 7]$ memiliki biaya maksimum: $a_2 = 2 + 4 = 6$.
• Untuk $k = 3$, partisi menjadi $[2, 4]$, $[1, 3, 6]$, dan $[5, 8, 7]$ memiliki biaya maksimum: $a_3 = 2 + 3 + 2 = 7$.
• Untuk $k = 4$, partisi menjadi $[2, 4]$, $[1, 3, 6]$, $[5, 8]$, dan $[7]$ memiliki biaya maksimum: $a_4 = 2 + 3 + 2 + 1 = 8$.
• Untuk $k > 4$, mudah dilihat bahwa $a_k = 8$.