좋은 부분 구간

길이가 $n$인 배열 $a[1..n]$이 주어진다. 배열의 원소는 모두 $1$ 이상 $n$ 이하의 정수이다. 부분 구간 $a[\ell..r]$은 위치 $\ell$부터 위치 $r$까지의 연속된 원소들이며, 양 끝을 포함한다.

부분 구간 $a[\ell..r]$이 $k$-good이려면 다음 조건을 모두 만족해야 한다.

• $r - \ell + 1 \ge 2 \cdot k$. 길이가 $2 \cdot k$ 이상이다.
• $a_{\ell} = a_{\ell + 1} = \cdots = a_{\ell + k - 1}$. 왼쪽 끝에서 적어도 $k$개의 원소가 서로 같다.
• $a_{r} = a_{r - 1} = \cdots = a_{r - k + 1}$. 오른쪽 끝에서 적어도 $k$개의 원소가 서로 같다.
• $a_{\ell} = a_r$. 양 끝의 값이 같다.

$1$부터 $\lfloor n/2 \rfloor$까지의 각 $k$에 대해, $k$-good인 부분 구간의 개수를 구하라.

첫 줄에 테스트 케이스의 개수 $t$ ($1 \le t \le 5 \cdot 10^5$)가 주어진다. 각 테스트 케이스는 다음과 같이 주어진다.

첫 줄에 정수 $n$ ($2 \le n \le 5 \cdot 10^5$)이 주어진다. 둘째 줄에 $n$개의 정수 $a_1, a_2, \ldots, a_n$ ($1 \le a_i \le n$)이 주어진다.

모든 테스트 케이스의 $n$을 합하면 $5 \cdot 10^5$을 넘지 않는다.

각 테스트 케이스마다 $\lfloor n/2 \rfloor$개의 정수를 한 줄에 출력한다. $k$번째 정수는 $k$-good인 부분 구간의 개수이다.