题目描述

在加勒比海地区的某个国家，所有决策都由公民大会上的简单多数投票决定（幸运的是，公民人数并不多）。当地的一个政党渴望以合法方式掌权，成功推动了选举制度的改革。其主要理由是该岛人口近期有所增加，举行公民大会不再那么容易。

改革的核心内容如下：从改革生效起，所有公民被划分为$K$（可能不等）个组。之后，每个问题都在各个组内进行投票。此外，如果一个组内超过半数的人投“赞成”票，那么该组就被视为投“赞成”票，否则视为投“反对”票。在每个组投票结束后，统计投“赞成”和“反对”的组的数量。如果投“赞成”票的组的数量大于组总数的一半，那么该问题的答案为肯定。

起初，岛上居民欣然接受了这个制度。但最初的喜悦消退后，一些负面问题逐渐显现。事实证明，推行该制度的政党的支持者能够影响选民分组的形成。因此，他们有机会在没有多数选民支持的情况下通过某些决策。

假设有三组选民，人数分别为5、5和7人。那么该政党只需在前两组中各安排3名支持者，这样它仅凭借6张“赞成”票就能通过一项决策，而在全民投票的情况下则需要9张“赞成”票。

你需要编写一个程序，根据给定的选民分组情况，确定该政党为了能在各个组中分配支持者以通过任何决策所需的最少支持者数量。

输入

本题的输入包含两行。第一行仅写有一个自然数$K$（$K \leq 101$），表示组的数量。第二行写有$K$个自然数，用空格隔开，这些数分别表示每个组中的选民人数。为了简化“多数票”的概念，我们规定组的数量以及每个组中的选民人数均为奇数。你也可以认为该岛的总人口不超过10001人 。

输出

你应输出一个自然数，即该政党为通过任何决策所需的最少支持者数量。

3
5 7 5

6

来源

乌拉尔国立大学2000年10月内部竞赛，初级组