题目限制

1000 ms 128 M

题目描述

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

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

输入格式

单组测试数据。
第一行包含一个整数n，表示鱼的数量。(1 ≤ n ≤ 2e6)
第二行有n个用空格分开的整数ai 表示第i条鱼的体重(1 ≤ ai ≤ 1e6)。

输出格式

输出一个整数代表结果。

数据范围

对于35%的数据，1≤n≤10，1 ≤ ai ≤ 100
对于55%的数据，1≤n≤10000
对于100%的数据，1 ≤ n ≤ 2e6，1 ≤ ai ≤ 1e6

输入样例

input example1:

3
3 4 5

input example2:

2
2 2

input example3:

5
2 1 4 3 5

输出样例

output example1:

2

output example2:

0

output example3:

2

样例解释

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