문제

You are given an array $a[1..n]$ consisting of $n$ integers from $1$ to $n$. Asubsegment $a[\ell..r]$ of the array is its consecutive part from position $\ell$ to position $r$, inclusive.

A subsegment $a[\ell..r]$ is$k$-good if the following conditions are satisfied:

• $r - \ell + 1 \ge 2 \cdot k$, so its length is at least $2 \cdot k$;
• $a_{\ell} = a_{\ell + 1} = a_{\ell + 2} = ... = a_{\ell + k - 1}$, so at least $k$ of its leftmost elements are equal to each other;
• $a_{r} = a_{r - 1} = a_{r - 2} = ... = a_{r - k + 1}$, so at least $k$ its rightmost elements are equal to each other;
• $a_{\ell} = a_r$, so its ends are equal.

For each $k$ from $1$ to $\left\lfloor\frac{n}{2}\right\rfloor$, find the number of $k$-good subsegments of the given array $a$.

입력

The first line contains an integer $t$ ($1 \le t \le 5 \cdot 10^5$), the number of test cases. The test cases follow.

The first line of each test case contains an integer $n$ ($2 \le n \le 5 \cdot 10^5$).

The second line consists of $n$ integers $a_1, a_2, \ldots, a_n$ ($1 \le a_i \le n$).

The sum of $n$ over all test cases does not exceed $5 \cdot 10^5$.

출력

For each test case, print a line with $\left\lfloor\frac{n}{2}\right\rfloor$ integers: the number of $k$-good subsegments for each corresponding $k$, starting from $1$.

제한

힌트