1025. 民主危机

时间限制: 1.0 秒

内存限制: 64 MB

背景

在加勒比海盆地的一个国家中，所有决策都是在公民大会上通过简单多数票通过的（幸运的是，公民人数并不多）。一个渴望以尽可能合法的方式上台的地方政党，成功实施了一些选举制度改革。主要理由是岛上人口最近增加了，召开公民大会不再容易。

改革的实质如下。从生效之日起，所有公民被分成$K$个（可能不相等的）组。然后每个问题在每个组中进行投票，而且，如果超过一半的组员投"赞成"票，则该组被视为投"赞成"票，否则被视为投"反对"票。在每个组投票后，计算投"赞成"票和"反对"票的组数。如果投"赞成"票的组数大于总组数的一半，则该问题的答案是肯定的。

起初，岛上的居民愉快地接受了这个系统。但当最初的喜悦消散后，一些负面特性变得明显起来。事实证明，引入该制度的政党的支持者可以影响选民群体的组成。因此，他们有机会在没有多数选民"赞成"的情况下实施某些决定。

让我们考虑三个选民组，分别包含5人、5人和7人。那么该政党只需要在前两个组中各拥有三名支持者。这样，它就能够仅用6张"赞成"票就实施一项决策，而在全民投票的情况下，这将需要9张"赞成"票。

问题

你需要编写一个程序，根据给定的选民划分，确定该政党支持者的最小数量，这些支持者在这些组中的某种分布下足以实施任何决策。

输入

第一行写有一个奇数$K$——组的数量（$1 \leq K \leq 101$）。第二行写有$K$个用空格分隔的奇数。这些数字定义了每个组中的选民数量。岛上的人口不超过9999人。

输出

你应该写出该政党支持者的最小数量，这些支持者可以实施任何决策。

样例

输入

3
5 7 5

输出

6