Bạn được cho một hoán vị $p$ có độ dài $n$. Với một đoạn con liên tiếp của $p$, định nghĩa chi phí của nó là độ dài của dãy con tăng dài nhất của đoạn con này. Với một phân hoạch của $p$ thành các đoạn con liên tiếp rời nhau, định nghĩa chi phí của nó là tổng chi phí của các đoạn con đó.

Định nghĩa $a_k$ là chi phí lớn nhất trong số các phân hoạch của $p$ thành $k$ đoạn con liên tiếp rời nhau khác rỗng.

Bạn cần tìm $a_k$ với mỗi $k$ từ $1$ đến $n$.

Dữ liệu vào

Dữ liệu vào gồm nhiều bộ dữ liệu. Dòng đầu tiên chứa một số nguyên duy nhất $t$ ($1 \le t \le 10^3$), là số lượng bộ dữ liệu. Mô tả của các bộ dữ liệu theo sau.

Dòng đầu tiên của mỗi bộ dữ liệu chứa một số nguyên $n$ ($1 \le n \le 10^5$).

Dòng thứ hai chứa $n$ số nguyên khác nhau $p_1, p_2, \dots, p_n$ ($1 \le p_i \le n$). Cùng nhau, chúng tạo thành một hoán vị của $1, 2, \dots, n$.

Tổng của $n$ trong tất cả các bộ dữ liệu không vượt quá $10^5$.

Dữ liệu ra

Với mỗi bộ dữ liệu, hãy in ra $a_1, a_2, \dots, a_n$ trên một dòng.

Ví dụ

Dữ liệu vào 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

Dữ liệu ra 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

Ghi chú

Xét bộ dữ liệu thứ ba với hoán vị $p = [2, 4, 1, 3, 6, 5, 8, 7]$:

• Với $k = 1$, đáp án chính là độ dài của dãy con tăng dài nhất trong $p$, tức là $a_1 = 4$.
• Với $k = 2$, cách phân hoạch thành $[2, 4]$ và $[1, 3, 6, 5, 8, 7]$ có chi phí lớn nhất: $a_2 = 2 + 4 = 6$.
• Với $k = 3$, cách phân hoạch thành $[2, 4]$, $[1, 3, 6]$, và $[5, 8, 7]$ có chi phí lớn nhất: $a_3 = 2 + 3 + 2 = 7$.
• Với $k = 4$, cách phân hoạch thành $[2, 4]$, $[1, 3, 6]$, $[5, 8]$, và $[7]$ có chi phí lớn nhất: $a_4 = 2 + 3 + 2 + 1 = 8$.
• Với $k > 4$, dễ thấy rằng $a_k = 8$.