题目描述

塔子哥又在玩游戏了！

和往常一样，游戏依旧有$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