有一个由 $n$ 个正长度线段组成的折叠棒。线段通过铰链（可伸缩的绳子）连接，允许在每个铰链处将线段折叠 180 度。包裹长度是指在铰链处进行一次或多次折叠后，折叠棒的长度。根据折叠策略的不同，包裹长度可能会有所不同。

你需要找到在以下折叠方式下的最小包裹长度：首先，将折叠棒的线段沿水平线放置。然后，从左到右顺时针折叠折叠棒。在折叠过程中，每个铰链左侧连接的线段要么顺时针旋转 180 度，要么保持不动。

例如，下图显示了一个四段折叠棒，其线段长度之和为 10。图中，从左到右的线段长度分别为 3、2、2 和 3，铰链标记为 ①、②、③。

在此示例中，折叠棒不能同时在铰链 ① 和 ② 处折叠。这是因为如果先在铰链 ① 处折叠，然后再在铰链 ② 处折叠，则穿过铰链 ② 的长度为 3 的线段将会断裂。如果仅在铰链 ② 处折叠，则包裹长度为 5。如果依次在铰链 ① 和 ③ 处折叠，则包裹长度为 4，如下图所示。

给定一个折叠棒的线段长度序列，编写一个程序输出该折叠棒的最小包裹长度。

输入格式

程序从标准输入读取数据。输入的第一行包含一个整数 $n$ ($2 \le n \le 100,000$)，表示折叠棒的线段数量。下一行包含 $n$ 个正整数，表示从左到右的线段长度序列。每个线段的长度不超过 20,000。

输出格式

程序将结果写入标准输出。仅打印一行，包含表示最小包裹长度的正整数。

样例

输入 1

4
3 2 2 3

输出 1

4

输入 2

5
1 1 1 1 1

输出 2

1

输入 3

7
1 3 2 3 4 2 2

输出 3

6