题目来源：OIClass

本题目 加强题目，题目范围进行修改，原标程可能无法通过！

问题描述

小 $P$ 同学在养殖一种非常凶狠的鱼，而且与其他鱼类不同，这种鱼越大越温顺，反而小鱼最凶残。当两条鱼相遇时，小鱼会不断撕咬大鱼，每一口都咬下与它自身等重的肉（小鱼保持体重不变），直到大鱼的体重小于这条小鱼（若两条鱼体重相同，一条鱼会将另一条撕咬殆尽）。

现在池塘中有 $n$ 条鱼，小 $P$ 想知道哪一对鱼相遇后，被咬的鱼剩余体重最大。

输入格式

第一行包含一个整数 $n$，表示鱼的数量。$(1 \le n \le 2e6$)

第二行有 $n$ 个用空格分开的整数 $a_i$ 表示第 $i$ 条鱼的体重。($1 \le a_i \le 1e6$)

输出格式

输出一个整数代表结果。

3
3 4 5

2

2
2 2

0

5
2 1 4 3 5

2

样例解释

当三条鱼的体重分别为 $3\ 4\ 5$ 时，不同对鱼相遇的结果分别是 $\{3,4\}=1\ \{3,5\}=2\ \{4,5\}=1$，所以只有第一条跟第三条鱼相遇时，最后大鱼的体重最大，结果为 $2$。

数据范围

对于 $35\%$ 的数据，$1\le n\le 10,1\le a_i \le 100$

对于 $100\%$ 的数据，$1\le n\le 20000,1\le a_i \le 1e18$