某一天妖怪部落的妖怪们为了争当妖王发生了内斗，每个妖怪都发了疯似的攻击同伴，在这种无休止的战斗里，活到最后的妖怪才可以当妖王。
已知部落里有n个妖怪，每个妖怪具有生命值hp和攻击力attack两种属性,且每个妖怪单次攻击的attack与其hp相同。例如当一个妖怪m1的hp为x，被另外一个hp为y的妖怪m2攻击后，m1的hp就会变成x-y，妖怪的hp<=0时立刻死亡退出战斗。每一轮战斗中一个存活的妖怪可以选择攻击其他任意一个存活的妖怪一次或者不发动攻击，直到只有一个妖怪存活时战斗结束。
求内斗完后的妖王hp值最低可能是多少。
输入描述:
第一行一个n（1≤n≤105），表示妖怪个数。
第二行每行n个数,第i个数ai表示第i只妖怪的hp值（1≤ai≤109）
输出描述:
一个数，表示妖王最低的hp值。
示例1
说明
第二只妖怪攻击其他所有妖怪，其他所有妖怪都不攻击，最后只有第二只存活。
示例2
说明
4攻击6，变成4 2；
2攻击4，变成2 2；
2攻击2，变成2 0；