学长的神之一手
时间限制：C/C++/Rust/Pascal 2秒，其他语言4秒
空间限制：C/C++/Rust/Pascal 256 M，其他语言512 M
64bit IO Format: %lld

题目描述

有 n 个房间相连，按顺序从 1 \sim n 编号。开始时，InHng 在 1 号房间，Cynthia 在 n 号房间，二人从两端相向而行，希望最终可以在某一房间相遇。游戏开始前，InHng 和 Cynthia 的血量都为 hp，当某一玩家到达房间 i 时，其将会减少 a_i 血量。当任意一名玩家的血量小于等于 0 时，游戏结束。
但他们的学长拥有 \lfloor \frac{n}{2} \rfloor 枚金币，在游戏开始前，学长可以通过神之一手，使用他已有的金币进行以下操作(金币不能为负数)：
  1. 花费 1 金币，使其中的一个房间不会减少血量；
  2. 花费 2 金币，使其中的一个房间的效果从减少 a_i 血量变为增加 a_i 血量；
请问 hp 至少为多少时，两人才可以在同一房间相遇。
注意：在相遇的房间，InHng 和 Cynthia 的血量都会受到该房间影响。

输入描述:

第一行输入一个 n(2 \leq n \leq 10^5)。
第二行输入 n 个数 a_1,a_2, \dots ,a_n(0 \leq a_i \leq 10^5)，数据保证 a_1=a_n=0 。

输出描述:

输出一个整数，表示两人在学长神之一手的帮助下可以相遇的 hp 的最小值。
示例1

输入

复制 
7
0 3 2 2 3 1 0

输出

复制 
2

说明

神之一手在 2 号房间花费 2 金币，在 5 号房间花费 1 金币。InHng 和 Cynthia 初始血量为 2，最终可以在 5 号房间相遇，相遇后，InHng 和 Cynthia 血量为 1，更少的初始血量无法相遇