生日蛋糕就是青春的墓碑

题目描述

没有人一起庆祝的生日只是平常的一天，这样的一天路明非已经过得很多了

在路明非生日的时候，一共收到了$n(1 \le n \le 10^6)$份礼物，每份礼物的价值为 $a_i(1 \le a_i \le 10^6)$，由于路明非是个衰仔，他的高兴程度只取决于收到的礼物的最大价值，即$max(a_1,a_2,…,a_n)$，小魔鬼为了让哥哥更加开心，决定对礼物进行任意次(可以为0次)操作： 取$1 \le i≠j \le n$ 中的 $a_i+a_j$ 为奇数，$a_i>0$ 为偶数，然后将 $a_i$ 减少 $x$，将$a_j$增加 $x$，当且仅当 $x \le a_i$。 请帮助小魔鬼找出任意次数操作后礼物，路明非的最大高兴程度。

输入格式

第一行一个整数n，表示礼物数量。 第二行n个整数$a_1,a_2...a_n$表示各个礼物的价值。

输出格式

输出任意次操作，路明非的最大高兴程度。

样例 #1

样例输入 #1

3
5 3 9

样例输出 #1

9

提示

在第一个测试用例中，没有一对塔满足应用操作所需的条件，因此无法执行操作。在这种情况下，答案为 max(5, 3, 9)=9。

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

在第三个测试案例中，可以进行以下操作： 对 i=2和j=1进行操作。 [1, 2, 2, 1]→[3, 0, 2, 1] 与 i=3和j=1的运算。 [3, 0, 2, 1]→[4, 0, 1, 1] 与 i=1和j=3的运算。 [4, 0, 1, 1]→[0, 0, 5, 1] max(0, 0, 5, 1) = 5 因此，答案是 5。