Problem 3671 --2020-2-小 C 的数组（array）-初中组

3671: 2020-2-小 C 的数组（array）-初中组

上一题 正确率: $31.82\%$ 下一题
"
Time Limit $1$ 秒/Second(s) Memory Limit $512$ 兆字节/Megabyte(s)
提交总数 $22$ 正确数量 $7$
裁判形式 标准裁判/Standard Judge 我的状态 尚未尝试
难度 分类标签

Description

小 C 终于成为一名萌新 OIer，最近他在学习数组。小 C 要练习数组。一次，小 C 得到了一个长度为 n 的数组 a。
现在，对于每一个下标 i，小 C 想找出比 i小且距离 i最近的下标 j，使得满足 ai ≠ aj，如果不存在，则 j = 0。记下标 i 对应的答案 fi = j，小 C 为了确保自己的程序正确，想让你来检查 f 数组。
可你不能告诉他整个答案，你只需要告诉他 f 数组所有元素的和即可

Input

共两行，第一行一个正整数 n，表示数组长度；
第二行 n 个正整数，第 i 个表示 ai。

Output

仅一行一个数，表示 f 数组所有元素的和。

Sample Input复制

6
1 1 2 3 2 1

Sample Output复制

14

提示

【样例 1 解释】
fi 依次为 (0, 0, 2, 3, 4, 5)，总和为 14。
【数据范围】
对于 40% 的数据：n ≤ 1000，1 ≤ ai ≤ 10，且保证数据随机；
对于 70% 的数据：n ≤ 106，1 ≤ ai ≤ 10，且保证数据随机；
对于 90% 的数据：n ≤ 106，1 ≤ ai ≤ 10；
对于 100% 的数据：n ≤ 106，1 ≤ ai ≤ 1000。
随机数据的生成方式如下：对于每一个 ai，等概率地从 1 到 10 中产生。

推荐代码 查看3671 所有题解 上传题解视频得图灵币

本题记录 用 户（点击查看用户） 运行号（点击购买题解） 时 间
算法最快[$83 $ms] ldy6314 764752 2021-10-11 09:25:18
内存最少[$5992 $KB] ldy6314 764752 2021-10-11 09:25:18
第一AC ldy6314 764223 2021-10-09 09:56:47
第一挑战 ldy6314 764223 2021-10-09 09:56:47

赛题来源/所属竞赛 S:合肥市信息学 N/A

竞赛编号 竞赛名称 竞赛时间 访问比赛