Dana jest jedna permutacja $p$ długości $n$. Dla spójnego podprzedziału permutacji $p$ zdefiniujmy jego koszt jako długość najdłuższego podciągu rosnącego tego podprzedziału. Dla podziału permutacji $p$ na rozłączne podprzedziały zdefiniujmy jego koszt jako sumę kosztów tych podprzedziałów.

Zdefiniujmy $a_k$ jako maksymalny koszt spośród podziałów permutacji $p$ na $k$ niepustych rozłącznych podprzedziałów.

Musisz wyznaczyć wartość $a_k$ dla każdego $k$ od $1$ do $n$.

Wejście

Wejście zawiera kilka przypadków testowych. Pierwszy wiersz zawiera jedną liczbę całkowitą $t$ ($1 \le t \le 10^3$), oznaczającą liczbę przypadków testowych. Poniżej znajduje się opis przypadków testowych.

Pierwszy wiersz każdego przypadku testowego zawiera liczbę całkowitą $n$ ($1 \le n \le 10^5$).

Drugi wiersz zawiera $n$ różnych liczb całkowitych $p_1, p_2, \dots, p_n$ ($1 \le p_i \le n$). Razem definiują one permutację liczb $1, 2, \dots, n$.

Suma wartości $n$ po wszystkich przypadkach testowych nie przekracza $10^5$.

Wyjście

Dla każdego przypadku testowego wypisz $a_1, a_2, \dots, a_n$ w jednym wierszu.

Przykład

Wejście 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

Wyjście 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

Uwagi

Rozważmy trzeci przypadek testowy z permutacją $p = [2, 4, 1, 3, 6, 5, 8, 7]$:

• Dla $k = 1$ odpowiedzią jest po prostu długość najdłuższego podciągu rosnącego w $p$, która wynosi $a_1 = 4$.
• Dla $k = 2$ podział na $[2, 4]$ oraz $[1, 3, 6, 5, 8, 7]$ osiąga maksymalny koszt: $a_2 = 2 + 4 = 6$.
• Dla $k = 3$ podział na $[2, 4]$, $[1, 3, 6]$ oraz $[5, 8, 7]$ osiąga maksymalny koszt: $a_3 = 2 + 3 + 2 = 7$.
• Dla $k = 4$ podział na $[2, 4]$, $[1, 3, 6]$, $[5, 8]$ oraz $[7]$ osiąga maksymalny koszt: $a_4 = 2 + 3 + 2 + 1 = 8$.
• Dla $k > 4$ łatwo zauważyć, że $a_k = 8$.