时间限制：2 sec

空间限制：1024 MB

题目描述

给定一个长度为 $N$ 的正整数序列 $A = (A_1, A_2, \ldots, A_N)$。高桥将重复执行以下操作，直到 $A$ 中仅剩一个或没有正整数为止：

• 将 $A$ 按降序排列。然后将最大的两个元素 $A_1$ 和 $A_2$ 各减去 $1$。

请求出高桥执行该操作的次数。

本题 $2 \leq N \leq 10^{2}$ 且 $1 \leq A_i \leq 10^{2}$ 。这是简单版数据范围，你可以使用模拟做出来这道题。

本题还有 $2 \leq N \leq 10^{5}$ 且 $1 \leq A_i \leq 10^{9}$ 。这是加强版数据范围，如果你学有余力可以想想这道题有没有更快的做法。

约束条件

• $2 \leq N \leq 10^{2}$
• $1 \leq A_i \leq 10^{2}$
• 所有输入值均为整数

输入格式

输入按以下格式从标准输入给出：

$N$

$A_1$   $A_2$   $\cdots$   $A_N$

输出格式

输出答案。

样例

样例1

4
1 2 3 3

4

操作过程如下：

• 第1次操作后，$A$ 为 $(2, 2, 2, 1)$
• 第2次操作后，$A$ 为 $(1, 1, 2, 1)$
• 第3次操作后，$A$ 为 $(1, 0, 1, 1)$
• 第4次操作后，$A$ 为 $(0, 0, 1, 0)$。$A$ 不再包含多于一个正整数，因此过程在此结束。

样例2

3
1 1 100

2