I. Intervals
time limit per test
2 seconds
memory limit per test
512 megabytes
input
standard input
output
standard output

You have a permutation $$$P$$$ consisting of $$$n$$$ unique numbers ranging from $$$0$$$ to $$$n-1$$$, inclusive. The set $$$P$$$ is defined as $$$P = \{p_1, p_2, \ldots, p_n\}$$$. The function $$$mex(S)$$$ is introduced to find the smallest non-negative integer that is not contained within a subset $$$S$$$ of $$$P$$$. For any interval $$$[i, j]$$$ within $$$P$$$, where $$$1 \le i \le j \le n$$$, the function $$$g(i, j)$$$ is defined as the mex of the subset of $$$P$$$ formed by the elements $$$p_i, p_{i+1}, \ldots, p_j$$$. Your goal is to determine the total count of intervals $$$[i, j]$$$ such that $$$g(i, j) = k$$$, where k is a non-negative integer.

To illustrate this with an example, consider $$$n = 5$$$ and $$$P = \{0, 1, 2, 3, 4\}$$$. We are interested in finding the number of intervals where $$$g(i, j) = 1$$$. The only interval that satisfies $$$g(0,0) = 1$$$ is $$$[0,0]$$$.

Input

The initial line of the input presents an integer $$$t~(1 \le t \le 10^4)$$$, which denotes the quantity of test cases. For each test case, the first line introduces a single integer $$$n~(2 \le n \le 10^6)$$$, representing the size of the permutation. Subsequently, the second line contains $$$n$$$ unique integers, ranging from $$$0$$$ to $$$n-1$$$, representing the permutation $$$P$$$.

It is assured that the cumulative total of $$$n$$$ values across all test cases will not surpass $$$1,000,000$$$.

Output

For each test case, you are required to output $$$n+1$$$ integers. These integers represent the solutions for $$$k$$$, ranging from $$$0$$$ to $$$n$$$.

Example
Input
1
5
0 1 2 3 4
Output
10 1 1 1 1 1