Julia 正在参与一项大型体育博彩竞赛，比赛涉及多场两队之间的对决。比赛之间没有并行场次，每位参与者每猜对一场比赛即可获得一分。Julia 此前表现出色，目前处于领先地位。现在她担心自己的好运即将耗尽，于是决定改变策略。

她与博彩店老板合作，老板会告诉她其他所有人的投注情况。每当 Julia 进行投注时，她会先查看目前得分最高的其他所有投注者的投注情况（当然不包括她自己），然后选择与多数人相同的队伍。如果出现平局，她会投注于她在那场比赛中更偏爱的那支队伍。

Julia 想知道，在最坏的情况下（即无论其他人如何投注，也无论比赛结果如何），她还能保证在多少场比赛中保持领先。在本题中，如果没有任何其他投注者的得分严格高于 Julia，我们就认为 Julia 处于领先地位。

例如，假设如样例 1 所示，Julia 最初有 3 分，另外两名投注者分别有 3 分和 2 分。对于第一场比赛，她会做出与那位有 3 分的投注者相同的选择。如果此人投注的队伍输了，而另一人投注的队伍赢了，那么所有人的得分都将变为 3 分。如果下一场比赛中，另外两人投注了不同的队伍，Julia 会投注于她偏爱的队伍，而这支队伍当然可能会输。因此，再过两场比赛后，她可能会失去领先地位。

输入格式

输入包含： 一行包含一个整数 $n$ ($3 \le n \le 10^5$)，表示参与投注的人数。 一行包含 $n$ 个整数 $p_1, \dots, p_n$ ($0 \le p_i \le 10^{16}$，对于每个 $i$)，表示所有参与博彩游戏的人的得分。其中第一个数字对应 Julia 的得分。

你可以假设在开始时，没有任何其他人的得分超过 Julia 的得分。

输出格式

输出 Julia 能够保证保持领先的比赛场数。

样例

输入 1

3
3 3 2

输出 1

1

输入 2

5
8 4 3 5 2

输出 2

6