P16993 [NWERC 2018] 倒霉下注 / Jinxed Betting

译自 [NWERC 2018](https://2018.nwerc.eu/) J 题。

Julia 正在为一项大型体育比赛下注，比赛由若干两两对战的队伍组成。比赛不会并行进行，每位下注者每猜对一场比赛就得到一分。Julia 最近运气很好，目前处于领先。现在她担心好运可能要结束了，于是决定改变策略。 她与一家博彩店老板合作，老板会告诉她其他所有人的下注情况。每当 Julia 要下注时，她会先查看目前分数最高的所有下注者（当然不包括她自己）的下注，然后选择其中多数人下注的队伍。如果出现平局，她就下注本场比赛两队中自己更喜欢的队伍。 Julia 想知道，在最坏情况下（也就是说，无论其他人如何下注、比赛结果如何），她还能够保证领先多少场比赛。对于本题，如果没有任何其他下注者的分数严格高于 Julia，我们就认为 Julia 处于领先。 例如，在样例输入 $1$ 中，Julia 初始有 $3$ 分，另外两名下注者分别有 $3$ 分和 $2$ 分。第一场比赛时，她会和另一名 $3$ 分下注者下同样的注。如果这个人下注了输的队，而另一个人下注了赢的队，那么三人的分数都会变成 $3$ 分。如果下一场比赛中另外两人下注不同队伍，Julia 会选择自己喜欢的队伍，而这当然可能输掉。因此再过两场比赛之后，她可能失去领先。

输入包括： - 一行一个整数 $n$（$3\le n\le 10^5$），表示参与下注的人数。 - 一行 $n$ 个整数 $p_1,\ldots,p_n$（对每个 $i$，$0\le p_i\le 10^{16}$），表示所有参与者的分数。其中第一个数是 Julia 的分数。保证一开始没有其他人的分数超过 Julia。

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

【数据规模与约定】 具体限制见输入格式。