该比赛已结束，您无法在比赛模式下递交该题目。您可以点击“在题库中打开”以普通模式查看和递交本题。

题目描述

小 A 拥有一棵包含 $n$ 个结点的有根完全二叉树，结点编号为 $1,2,\dots,n$，根结点编号为 $1$。

树上的每个结点都有一个状态值：

• 0 表示结界稳定；
• 1 表示结界破损。

小 A 至多可以施展一次“大治愈术”。如果他选择某个结点 $x$ 施法，那么以 $x$ 为根的整棵子树中，所有结点的状态都会被反转，也就是 0 变成 1，1 变成 0。

你也可以选择完全不施法。

请你求出，在最优决策下，整棵树中最多能有多少个稳定结点，也就是状态为 0 的结点数量。

输入格式

第一行一个正整数 $n$，表示结点数量。

第二行 $n$ 个整数 $s_1,s_2,\dots,s_n$，表示编号 $1$ 到 $n$ 的结点初始状态。

输出格式

输出一行，一个整数，表示至多施展一次法术后，树上最多的稳定结点数量。

5
1 1 0 1 0

3

7
0 0 1 1 1 1 1

5

说明/提示

样例 1 解释：

初始时状态为 0 的结点有两个，分别是结点 $3$ 和结点 $5$。如果对结点 $2$ 施法，那么以 $2$ 为根的子树包含结点 $2,4,5$，它们的状态会从 1,1,0 变成 0,0,1。此时整棵树的状态变成 1 0 0 0 1，共有 $3$ 个稳定结点，这是最优答案。

样例 2 解释：

初始时稳定结点有 $2$ 个。若对结点 $3$ 施法，则结点 $3,6,7$ 的状态会从 1,1,1 变成 0,0,0，总稳定结点数量变成 $5$，这是最优结果。

对于 $40\%$ 的测试点，保证 $1 \le n \le 10^3$。

对于所有测试点，保证 $1 \le n \le 2 \times 10^5$，输入数据满足完全二叉树性质。