问题描述

在一个古老的部落里，有一个关于天气之子的试炼。

试炼将会给出连续 $n$ 天的天气情况。每种天气用一个正整数表示，相同的正整数表示同一种天气。

每天开始前，参与试炼的成员都需要对当天的天气进行预测。预测准确次数最多的人将成为部落的“天气之子”。

你设计了一种预测策略：

• 第一天：预测为 $1$

• 从第二天开始：

  1. 如果前一天预测成功，则今天的预测保持不变；

  2. 如果前一天预测失败，则统计前面所有天中出现次数最多的天气：

     • 若有多种天气出现次数相同，则选择第一次出现位置最靠后的那一种天气
     • 将今天的预测修改为该天气

请你计算该策略下，预测成功的总天数。

输入格式

• 第一行一个正整数 $n$，表示天数
• 第二行 $n$ 个正整数 $a_1, a_2, \dots, a_n$，表示每天的实际天气

输出格式

输出一个整数，表示预测成功的天数。

样例输入1

5
1 2 1 2 2

样例输出1

2

样例输入2

2
2 2

样例输出2

1

说明

预测过程如下：

• 第 1 天：预测 $1$（成功）
• 第 2 天：延续预测 $1$（失败）
• 第 3 天：前两天中 $1$ 和 $2$ 各出现 1 次，$2$ 第一次出现更晚 → 预测 $2$（失败）
• 第 4 天：前三天中 $1$ 出现 2 次 → 预测 $1$（失败）
• 第 5 天：前四天中 $1$ 和 $2$ 各出现 2 次，$2$ 第一次出现更晚 → 预测 $2$（成功）

共成功 $2$ 天。

评测数据规模