题目描述

当你 AK 了 PTOI2023R1 正式比赛之后，你很无聊，和题目中小朋友玩起了分糖果的小游戏，不过正式赛中 小 H 的愤怒值变成了 小 C 和 小 H 的愉悦值，不过这次有 $n$ 种不同的糖果，第 $i$ 种糖果有 $a_i$ 个，对于每个糖果你可以选择分发给小 C 或者 小 H。所有的糖果分发完毕后，当 小 C 或 小 H 手上的某一种糖果有且仅有一个时，他的愉悦值就增加一点，请问是否存在使小 C 和 小 H 愉悦值相同的分糖果方案？

输入格式

共两行，第一行给出一个正整数 $n$ 表示糖果一共有 $n$ 种。

第二行包含 $n$ 个正整数，分别给出每种糖果的数量 $a_i$ 。

输出格式

若存在使小 C 和 小 H 愉悦值相同的分糖果方案请输出数字 $1$ ，若不存在则输出数字 $0$ 。

样例

3
1 1 1

0

样例 1 解释

共有 $3$ 种糖果，每种糖果只有一个，所以你无论怎么分发糖果，小 C 和 小 H 的愉悦值都不可能相等，故不存在使小 C 和 小 H 愉悦值相同的分糖果方案，输出 $0$ 。

4
2 2 2 2

1

样例 2 解释

共有 $4$ 种糖果，给小 C 每种糖果发 $1$ 个，给小 H 每种糖果发 $1$ 个，两个人的愉悦值都等于 $4$ ，故存在使小 C 和 小 H 愉悦值相同的分糖果方案，输出 $1$ 。

4
6 6 6 6

1

样例 3 解释

共有 $4$ 种糖果，第 $1,2$ 种糖果给小 C 发 $1$ 个，给小 H 发 $5$ 个，第 $3,4$ 种糖果给小 C 发 $5$ 个，给小 H 发 $1$ 个 ，两个人的愉悦值都等于 $2$ ，故存在使小 C 和 小 H 愉悦值相同的分糖果方案，输出 $1$ 。

数据范围

对于全部数据，保证 $1 \le n,a_i \le 10^5$ 。