题目描述

徐老师最近在玩的游戏里推出了一个免费的"幸运数字"活动，活动一共持续 n 天，每天玩家可以选择一个数字作为自己的幸运数字 活动会在每天晚上公布当天的获奖数字，如果玩家选择的幸运数字和获奖数字是同一个，玩家就可以获得 1 金币的奖励现在徐老师提前做出了他准备选择幸运数字的方法：

1. 第一天选择 1 作为自己的幸运数字
2. 对于第 i(i>1)天，如果第 i-1天的的幸运数字猜对了，则依旧选择这个幸运数字
3. 对于第 i(i>1)天，如果第 i-1天的幸运数字猜错了，则统计前面所有的获奖数字，选择出现次数最多的获奖数字作为第 i 天的幸运数字，如果存在多个获奖数字出现次数一样，则选择其中最后一次出现的获奖数字。

现在徐老师想知道，自己会获得多少金币？

输入格式（文件名：lucky.in）

输入第一行包含一个整数n ，表示活动的天数。

第二行包含n 个数字 $a_i$，分别表示每一天的获奖数字。

输出格式（文件名：lucky.in）

输出一个整数，表示徐老师能获得多少金币。

5
1 2 1 2 2

2

提示

第一天选 1

第二天因为第一天中奖了，所以依旧选 1

第三天因为第二天没中奖，此时获奖数字中 1 和 2 各出现一次，选其中最晚出现的 2

第四天因为第三天没中奖，此时获奖数字中 1 出现 2 次最多，所以选 1

第五天因为第四天没中奖，此时获奖数字中 1 和 2 各出现 2 次，选其中最晚出现的 2

中奖的天数为第一天和第五天，所以能获得 2 个金币。

1 ≤ n ≤ $10^6$

1 ≤ $a_i$ ≤ $10^5$