C - Different Neighbor Editorial /

Time Limit: 2 sec / Memory Limit: 1024 MiB

配点 : 300 点

問題文

数直線上の座標 1, 2, \ldots, N に 1 個ずつ点があり、座標 i にある点を点 i と呼びます。

各点には色がついており、点 i の色は C_i です。ただし、C_1, C_2, \ldots, C_N に現れる値は 2 種類以上あります。

各 i = 1, 2, \ldots, N について、点 i と異なる色の点のうち、点 i からの距離が最も短いものまでの距離を求めてください。

制約

  • 2 \leq N \leq 3 \times 10^5
  • 1 \leq C_i \leq N
  • C_1, C_2, \ldots, C_N に現れる値は 2 種類以上
  • 入力される値はすべて整数

入力

入力は以下の形式で標準入力から与えられる。

N
C_1 C_2 \ldots C_N

出力

i = 1, 2, \ldots, N に対する答えをこの順に空白区切りで出力せよ。


入力例 1

6
1 1 2 3 3 3

出力例 1

2 1 1 1 2 3

点 1 と異なる色の点のうち、点 1 から最も近い点は点 3 であり、点 1 からの距離は 2 です。

点 2 と異なる色の点のうち、点 2 から最も近い点は点 3 であり、点 2 からの距離は 1 です。

点 3 と異なる色の点のうち、点 3 から最も近い点は点 2 と点 4 であり、点 3 からの距離は 1 です。

点 4 と異なる色の点のうち、点 4 から最も近い点は点 3 であり、点 4 からの距離は 1 です。

点 5 と異なる色の点のうち、点 5 から最も近い点は点 3 であり、点 5 からの距離は 2 です。

点 6 と異なる色の点のうち、点 6 から最も近い点は点 3 であり、点 6 からの距離は 3 です。

したがって、2, 1, 1, 1, 2, 3 をこの順に空白区切りで出力します。


入力例 2

7
4 2 3 3 3 4 4

出力例 2

1 1 1 2 1 1 2

Score : 300 points

Problem Statement

There is one point at each of the coordinates 1, 2, \ldots, N on a number line, and the point at coordinate i is called point i.

Each point has a color, and the color of point i is C_i. Here, at least two distinct values appear in C_1, C_2, \ldots, C_N.

For each i = 1, 2, \ldots, N, find the distance from point i to the nearest point whose color is different from that of point i.

Constraints

  • 2 \leq N \leq 3 \times 10^5
  • 1 \leq C_i \leq N
  • At least two distinct values appear in C_1, C_2, \ldots, C_N.
  • All input values are integers.

Input

The input is given from Standard Input in the following format:

N
C_1 C_2 \ldots C_N

Output

Print the answers for i = 1, 2, \ldots, N in this order, separated by spaces.


Sample Input 1

6
1 1 2 3 3 3

Sample Output 1

2 1 1 1 2 3

Among the points whose color is different from that of point 1, the nearest to point 1 is point 3, and its distance from point 1 is 2.

Among the points whose color is different from that of point 2, the nearest to point 2 is point 3, and its distance from point 2 is 1.

Among the points whose color is different from that of point 3, the nearest to point 3 are points 2 and 4, and their distance from point 3 is 1.

Among the points whose color is different from that of point 4, the nearest to point 4 is point 3, and its distance from point 4 is 1.

Among the points whose color is different from that of point 5, the nearest to point 5 is point 3, and its distance from point 5 is 2.

Among the points whose color is different from that of point 6, the nearest to point 6 is point 3, and its distance from point 6 is 3.

Thus, print 2, 1, 1, 1, 2, 3 in this order, separated by spaces.


Sample Input 2

7
4 2 3 3 3 4 4

Sample Output 2

1 1 1 2 1 1 2