33OJ
登录 注册

#ABC485C. 异色最近点

异色最近点

异色最近点

题目描述

在数轴的坐标 1,2,…,N1,2,\ldots,N 上各有一个点,坐标 ii 处的点称为点 ii。每个点都有一个颜色,点 ii 的颜色为 CiC_i。这里 C1,C2,…,CNC_1,C_2,\ldots,C_N 中至少出现两种不同的值。

对每个 i=1,2,…,Ni=1,2,\ldots,N,求出从点 ii 到「颜色与点 ii 不同的点」的最近距离。

输入格式

输入第一行为一个整数 NN。

第二行为 NN 个整数 C1,C2,…,CNC_1,C_2,\ldots,C_N。

输出格式

输出一行 NN 个整数,依次为 i=1,2,…,Ni=1,2,\ldots,N 的答案,相邻两个整数之间用一个空格隔开。

6
1 1 2 3 3 3
2 1 1 1 2 3

样例 1 解释

  • 点 11 的最近异色点是点 33,距离为 22;
  • 点 22 的最近异色点是点 33,距离为 11;
  • 点 33 的最近异色点是点 22 与点 44,距离为 11;
  • 点 44 的最近异色点是点 33,距离为 11;
  • 点 55 的最近异色点是点 33,距离为 22;
  • 点 66 的最近异色点是点 33,距离为 33。
7
4 2 3 3 3 4 4
1 1 1 2 1 1 2

数据范围

对于所有测试数据,保证:

  • 2≤N≤3×1052 \le N \le 3 \times 10^5;
  • 1≤Ci≤N1 \le C_i \le N;
  • C1,C2,…,CNC_1,C_2,\ldots,C_N 中至少出现两种不同的值;
  • 所有输入值均为整数。

子任务

本题共 20 个测试点,按测试点计分:

测试点 分值 每个测试点 特殊性质
1∼61 \sim 6 3030 55 N≤2000N \le 2000
7∼207 \sim 20 7070 无特殊限制

每个测试点单独评分,全部测试点的得分之和即为本题得分。