#1520. 徐老师的幸运数字
-
ID: 1520
Type: Default
1000ms
256MiB
Tried: 2
Accepted: 1
Difficulty: 10
Uploaded By:
sulaoshi
Tags> 徐老师的幸运数字
说明
徐老师最近在玩的游戏里推出了一个免费的"幸运数字"活动活动一共持续 $n$ 天，每天玩家可以选择一个数字作为自己的幸运数字
活动会在每天晚上公布当天的获奖数字，如果玩家选择的幸运数字和获奖数字是同一个，玩家就可以获得 $1$ 金币的奖励
现在徐老师提前做出了他准备选择幸运数字的方法：
1. 第一天选择 $1$ 作为自己的幸运数字
2. 对于第 $i(i>1)$ 天，如果第 $i - 1$ 天的的幸运数字猜对了，则依旧选择这个幸运数字
3. 对于第 $i(i>1)$ 天，如果第 $i - 1$ 天的幸运数字猜错了，则统计前面所有的获奖数字，选择出现次数最多的获奖数字作为第 $i$ 天的幸运数字，如果存在多个获奖数字出现次数一样，则选择其中最后一次出现的获奖数字
现在徐老师想知道，自己会获得多少金币？
输入格式
输入第一行包含一个整数 $n$，表示活动的天数第二行包含 $n$ 个数字$a_i$，分别表示每一天的获奖数字
| 数据点编号 | $n$的范围 | $a_i$编号范围 |
| :----: | :----: | :----: |
| $1 \sim 2$ | $1 \leq n \leq 10$ | $1 \leq a_i \leq 10$ |
| $3 \sim 5$ | $1 \leq n \leq 10^3$ | $1 \leq a_i \leq 10^3$ |
| $6 \sim 10$ | $1 \leq n \leq 10^6$ | $1 \leq a_i \leq 10^5$ |
输出格式
输出一个整数，表示徐老师能获得多少金币样例
5
1 2 1 2 22提示
第一天选 $1$第二天因为第一天中奖了，所以依旧选 $1$
第三天因为第二天没中奖，此时获奖数字中 $1$ 和 $2$ 各出现一次，选其中最晚出现的 $2$
第四天因为第三天没中奖，此时获奖数字中 $1$ 出现 $2$ 次最多，所以选 $1$
第五天因为第四天没中奖，此时获奖数字中 $1$ 和 $2$ 各出现 $2$ 次，选其中最晚出现的 $2$
中奖的天数为第一天和第五天，所以能获得 $2$ 个金币