길이가 $n$인 하나의 순열 $p$가 주어집니다. $p$의 연속 부분구간에 대해, 그 비용을 해당 부분구간의 가장 긴 증가하는 부분 수열(LIS)의 길이로 정의합니다. $p$를 서로소인 연속 부분구간들로 분할한 것에 대해, 그 비용을 이 부분구간들의 비용의 합으로 정의합니다.

$p$를 $k$개의 비어 있지 않은 서로소인 연속 부분구간으로 분할하는 모든 방법 중 최대 비용을 $a_k$로 정의합니다.

$1$부터 $n$까지의 각 $k$에 대해 $a_k$를 구해야 합니다.

입력

입력은 여러 개의 테스트 케이스를 포함합니다. 첫 번째 줄에는 테스트 케이스의 개수를 나타내는 하나의 정수 $t$($1 \le t \le 10^3$)가 주어집니다. 이어서 테스트 케이스들의 설명이 주어집니다.

각 테스트 케이스의 첫 번째 줄에는 정수 $n$($1 \le n \le 10^5$)이 주어집니다.

두 번째 줄에는 $n$개의 서로 다른 정수 $p_1, p_2, \dots, p_n$($1 \le p_i \le n$)이 주어집니다. 이들은 함께 $1, 2, \dots, n$의 순열을 이룹니다.

모든 테스트 케이스에서 $n$의 합은 $10^5$을 넘지 않습니다.

출력

각 테스트 케이스마다 한 줄에 $a_1, a_2, \dots, a_n$을 출력합니다.

예제

입력 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

출력 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

참고

순열 $p = [2, 4, 1, 3, 6, 5, 8, 7]$이 주어지는 세 번째 테스트 케이스를 살펴봅시다:

• $k = 1$일 때, 답은 단순히 $p$의 가장 긴 증가하는 부분 수열의 길이인 $a_1 = 4$입니다.
• $k = 2$일 때, $[2, 4]$와 $[1, 3, 6, 5, 8, 7]$로 분할하는 것이 최대 비용을 가집니다: $a_2 = 2 + 4 = 6$.
• $k = 3$일 때, $[2, 4]$, $[1, 3, 6]$, 그리고 $[5, 8, 7]$로 분할하는 것이 최대 비용을 가집니다: $a_3 = 2 + 3 + 2 = 7$.
• $k = 4$일 때, $[2, 4]$, $[1, 3, 6]$, $[5, 8]$, 그리고 $[7]$로 분할하는 것이 최대 비용을 가집니다: $a_4 = 2 + 3 + 2 + 1 = 8$.
• $k > 4$일 때, $a_k = 8$임을 쉽게 알 수 있습니다.