思路：模拟

给定$n$个关卡，每个关卡BOSS血量为$a_i$，当我们挑战第$i$关时，假设我们当前有$k$点血量，如果$k\gt a_i$，那么我们会恢复$k-a_i$点血，否则会扣除$a_i-k$点血。当血量小于0时，游戏失败。求通关的最少初始血量。

显然，在该规则下，我们初始血量越高，通关机会越大，因此初始血量是有单调性的，于是可以考虑二分的做法。

当二分当前初始血量时，可以根据题意$O(N)$的去判断该血量能否通关(根据题意进行模拟即可)，因此时间复杂度也是能够接受的。

时间复杂度为$O(Nlog(N))$。

题目描述

塔子哥又在玩游戏了！

和往常一样，游戏依旧有$n$关，每关有一个$a_i$血的BOSS，塔子哥最开始依旧有$k$滴血！

当挑战第$i$个BOSS时，如果塔子哥当前血量$x>a_i$，那么塔子哥会恢复$x-a_i$血！

否则，塔子哥会扣除$a_i-x$血！

当塔子哥血量低于0时，游戏失败！

塔子哥想知道，初始血量最低为多少时，能通关这个游戏？

输入描述

第一行为一个正整数$n\le10^5$，代表关卡数量

第二行为$n$个正整数$1 <= a_i <= 10^5$，代表每关BOSS血量

输出描述

一个正整数，代表初始最低血量

示例1

输入

3
3 3 4

输出

3