题目描述

在 Asuna 生日时，她的 $n$ 位仰慕者每人赠送了一座塔。第 $i$ 位仰慕者赠送的塔高度为 $a_i$。

Asuna 将礼物的美观度定义为 $\max(a_1, a_2, \ldots, a_n)$。她可以执行以下操作任意次数（包括零次）：

• 选择满足 $1 \leq i \neq j \leq n$ 的两个下标，使得 $a_i + a_j$ 为奇数且 $a_i > 0$。随后将 $a_i$ 减少 $1$，并将 $a_j$ 增加 $1$。

容易验证，在操作过程中塔的高度始终保持非负。请帮助 Asuna 求出经过任意次操作后可能达到的最大美观度。

输入格式

第一行包含一个整数 $n$ ($1 \leq n \leq 2 \cdot 10^5$) —— Asuna 的仰慕者数量。

第二行包含 $n$ 个整数 $a_1, a_2, \ldots, a_n$ ($1 \leq a_i \leq 10^9$) —— 各塔的高度。

输出格式

对于每个测试用例，输出一个整数：Asuna 能获得的最大美观度。

输入输出样例

3
5 3 9

2
3 2

4
1 2 2 1

5
5 4 3 2 9

9

5

5

21

说明/提示

第一个测试用例中，没有满足操作条件的塔对，因此无法进行任何操作。此时答案为 $\max(5, 3, 9) = 9$。

第二个测试用例中，可以对 $i=2$ 和 $j=1$ 执行两次操作。操作后数组变为：$a = [5, 0]$，因此答案为 5。

第三个测试用例中，可以执行以下操作序列：

1. 对 $i=1$ 和 $j=2$ 执行操作：$$[1, 2, 2, 1] \quad \rightarrow \quad [0, 3, 2, 1]$$
2. 对 $i=3$ 和 $j=2$ 执行操作：$$[0, 3, 2, 1] \quad \rightarrow \quad [0, 4, 1, 1]$$
3. 对 $i=3$ 和 $j=2$ 执行操作：$$[0, 4, 1, 1] \quad \rightarrow \quad [0, 5, 0, 1]$$

此时 $\max(0, 5, 0, 1) = 5$，因此答案为 5。