B. Making Towers

time limit per test:1 second

memory limit per test:256 megabytes

input:standard input

output:standard output

You have a sequence of n colored blocks. The color of the i-th block is ci, an integer between 1 and n.

You will place the blocks down in sequence on an infinite coordinate grid in the following way.

1. Initially, you place block 1 at (0,0).
2. For 2≤i≤n, if the (i−1)-th block is placed at position (x,y), then the ii-th block can be placed at one of positions (x+1,y), (x−1,y), (x,y+1) (but not at position (x,y−1), as long no previous block was placed at that position.

A tower is formed by ss blocks such that they are placed at positions (x,y),(x,y+1),…,(x,y+s−1) for some position  and integer ss. The size of the tower is ss, the number of blocks in it. A tower of color r is a tower such that all blocks in it have the color r.

For each color r from 1 to n, solve the following problem independently:

• Find the maximum size of a tower of color r that you can form by placing down the blocks according to the rules.

Input

The first line contains a single integer t (1≤t≤104) — the number of test cases.

The first line of each test case contains a single integer n (1≤n≤105).

The second line of each test case contains n integers c1,c2,…,cn (1≤ci≤n).

It is guaranteed that the sum of n over all test cases does not exceed 2⋅105.

Output

For each test case, output n integers. The r-th of them should be the maximum size of an tower of color r you can form by following the given rules. If you cannot form any tower of color r, the r-th integer should be 00.

Example

input

Copy

6

7

1 2 3 1 2 3 1

6

4 2 2 2 4 4

1

1

5

5 4 5 3 5

6

3 3 3 1 3 3

8

1 2 3 4 4 3 2 1

output

Copy

3 2 2 0 0 0 0

0 3 0 2 0 0

1

0 0 1 1 1

1 0 4 0 0 0

2 2 2 2 0 0 0 0

Note

In the first test case, one of the possible ways to form a tower of color 1 and size 3 is:

• place block 1 at position (0,0);
• place block 2 to the right of block 1, at position (1,0);
• place block 3 above block 2, at position (1,1);
• place block 4 to the left of block 3, at position (0,1);
• place block 5 to the left of block 4, at position (−1,1);
• place block 6 above block 5, at position (−1,2);
• place block 7 to the right of block 6, at position (0,2).

The blocks at positions (0,0), (0,1), and (0,2) all have color 1, forming an tower of size 3.

In the second test case, note that the following placement is not valid, since you are not allowed to place block 6 under block 5:

It can be shown that it is impossible to form a tower of color 4 and size 3.

Time is 1s, Large amount of data , My algorithm for this problem is right. It is compressed to （O(t*n)） So much time , Writing this question requires a little bit of Dynamic Planning .

First, explain that the distance between a color block and the next same color block must be an odd number , Ability is color block plus 1.

I thought it was really difficult to draw by hand , Please put yourself on the draft paper , Just draw according to the title .

（ You can refer to the first sample figure ）

#include <iostream>
using namespace std;
int main()
{
    int t;
    cin >> t;
    while (t > 0)                                           /*times:O(t*n)*/
    {
        int n;
        cin >> n;
        int r[100001];                                     /* Color block size */
        int data1[100001];
        int dp[100001];                                    /* Location of last status */
        int vis[100001];                                   /* Have you ever visited */
        for(int i=1;i<=n;i++)
        {
            r[i]=0;
            dp[i]=0;
            vis[i]=0;
            cin>>data1[i];
        }
        for(int i=1;i<=n;i++)
        {
            if(vis[data1[i]]==0)                               /* First visit , Let's save the status this time , Save it for the next visit */
            {
                dp[data1[i]]=i;
                r[data1[i]]=1;                                 /* Just visit for the first time , Let's set the color block to 1, So as not to add */
            }
            else
            {
                int temp=i;                                    /*temp It means where the position is this time */
                if((temp-dp[data1[i]])==1)                     /* The distance between this position and the last position is 1,r[data1[i]]+1*/
                {
                    r[data1[i]]++;
                    dp[data1[i]]=temp;                        /*dp[data1[i]] Express data1[i] Last position of */
                }
                else
                {
                    if((temp-dp[data1[i]])%2!=0)             /* Distance is odd ,r[data1[i]]++*/
                    {
                        r[data1[i]]++;
                        dp[data1[i]]=temp;
                    }
                }
            }
            vis[data1[i]]++;                                 /* I visited once , Add 1*/
        }
        for (int i = 1; i <= n; i++)
        {
            cout << r[i] << " ";
        }
        cout << endl;
        t--;
    }
    return 0;
}