33353번 - Good Subsegments 다국어

문제

You are given an array $a[1..n]$ consisting of $n$ integers from 1ドル$ to $n$. A subsegment $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ドル$.

제한

힌트