← 返回题目列表

Codeforces · 2092/C

C. 亚丝娜与蚊子们

中文机器翻译题面 查看原题

为了庆祝她的生日,亚丝娜的每位 $$$n$$$ 崇拜者都送给她一座塔。从第 $$$i$$$ 位崇拜者开始,塔的高度等于 $$$a_i$$$。

亚丝娜对收到的礼物的美丽程度评价为$$$\max(a_1, a_2, \ldots, a_n)$$$。她可以执行以下操作任意次数(可能为零)。

  • 取 $$$1 \le i \neq j \le n$$$ 使得 $$$a_i + a_j$$$ 为奇数且 $$$a_i \gt 0$$$,然后将 $$$a_i$$$ 减少 $$$1$$$ 并增加 $$$a_j$$$ $$$1$$$。
很容易看出,塔的高度在操作过程中保持非负值。

帮助亚丝娜在多次操作后找到礼物的最大可能的美丽!

输入

每个测试由多个测试用例组成。输入数据的第一行包含一个整数 $$$t$$$ ($$$1 \le t \le 10^4$$$) — 测试用例的数量。测试用例的描述如下。

每个测试用例的第一行包含一个整数 $$$n$$$ ($$$1 \leq n \leq 2 \cdot 10^5$$$) — 亚丝娜的崇拜者数量。

每个测试用例的第二行包含 $$$n$$$ 整数 $$$a_1, a_2, \ldots, a_n \ (1 \le a_i \le 10^9)$$$ — 塔的高度。

保证所有测试用例的 $$$n$$$ 总和不超过 $$$2 \cdot 10^5$$$。

输出

对于每个测试用例,输出一个整数:亚丝娜可以达到的礼物美感的最大值。

示例

输入
复制

4
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。