Good Subsegments

Time limit2sMemory limit2048 MB

Summary

For each k, count subsegments of length at least 2k whose first k elements are equal, whose last k elements are equal, and whose two end values match.

Level: Medium7 of 10
Topics: Hash map, Prefix sum, Array
Solved: No attempts yet

Statement

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

A subsegment $a[\ell..r]$ is $k$ -good if all of the following hold:

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

For each $k$ from $1$ to $\lfloor n/2 \rfloor$ , find the number of $k$ -good subsegments of $a$ .

Input

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 contains $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$ .

Output

For each test case, print one line with $\lfloor n/2 \rfloor$ integers. The $k$ -th integer is the number of $k$ -good subsegments.

Examples1

Example 1

Input

4
10
1 2 2 2 2 2 3 2 2 2
6
1 1 1 2 1 1
9
2 2 1 1 1 2 2 1 1
10
3 2 3 2 4 2 10 10 10 10

Expected output

28 11 3 0 0
10 2 0
16 3 0 0
10 1 0 0 0