Problem C. 最长高塔

时间限制：1000ms

内存限制：128MB

Background

一天小明正在用田字格练字，练了一段时间后，小明突然看见了书桌旁的蜡笔，于是小明打算休息一下。小明想用不同的蜡笔涂满不同的方格，这时小明的老师走了进来，发现小明在偷懒，于是想教训一下小明，但是他也不想打击小明发展其他兴趣的尝试。小明发现老师来了之后很害怕，以为老师会责骂他，但是老师却对他说...

Description

你看现在若干种不同颜色的蜡笔，但是每种蜡笔都快用完了，而我之后还需要用，所以我会规定你使用蜡笔的次数。你只能用这些蜡笔 \(n\) 次，第 \(i\) 次只能用第 \(c_i\) 种蜡笔（ \(1 \leq c_i \leq n\) ）。现在选取合适的一个方格作为 ( \(0,0\) ) 点，并用蜡笔涂满这个方格（这是第一次）。接下来的第 \(i\) 次（ \(2 \leq i \leq n\) ），如果第 \(i-1\) 次涂满了 \((x,y)\) 这个方格，那么这次你只能涂满 \((x+1,y), (x-1,y), (x,y+1)\) 这三个方格之一。现在我随便选取一个颜色，你能用这个颜色画出最长的高塔出来吗。

小明觉得这个问题很难，便求助一旁的你。同时为了应对老师的提问，小明想知道所有情况的答案。

注：高塔即为一段颜色相同的竖条。具体来说如果方格纸上 \((x,y),(x,y+1), ... ,(x,y+s-1)\) 这些位置都被同一种颜色 \(r\) 涂满的话，那么则称这是一个大小为 \(s\) ，颜色为 \(r\) 的高塔。

Input

第一行一个整数 \(n\) ，含义见描述；

第二行 \(n\) 个整数，分别为 \(c_1, c_2, ..., c_n\) .

Output

输出 \(n\) 个整数，用空格隔开，第 \(i\) 个整数代表用 \(i\) 种颜色能画出来的最长颜色为 \(i\) 的高塔的大小。

注意， 每一种颜色得出的结果是独立的，代表着老师选取的是对应的颜色 。

Samples

Sample Input 1

7
1 2 3 1 2 3 1

Sample Output 1

3 2 2 0 0 0 0 

解释：由于规定使用的蜡笔颜色不包括第 \(4\) ~ \(7\) 种，所以答案中的第 \(4\) ~ \(7\) 个数都为0；当老师选取的是第 \(1\) ~ \(3\) 种颜色时，分别得到的符合要求的其中一种画法分别如下图所示。

Sample Input 2

6
4 2 2 2 4 4

Sample Output 2

0 3 0 2 0 0

Sample Input 3

50
43 44 22 49 31 16 3 36 1 49 45 49 42 30 23 46 47 8 26 3 4 27 47 50 21 23 47 9 23 42 35 30 35 5 8 7 32 32 50 41 19 43 33 4 38 23 7 29 34 38

Sample Output 3

1 0 2 2 1 0 2 2 1 0 0 0 0 0 0 1 0 0 1 0 1 1 4 0 0 1 1 0 1 1 1 2 1 1 1 1 0 2 0 0 1 2 2 1 1 1 1 0 1 2

Data range

对于50% 数据，\(1 \leq n \leq 100\)，对于 100% 数据，\(1 \leq n \leq 2 \times 10^5\)。