题目描述

薯条哥超级喜欢玩游戏，最近又开发了一款新的游戏。

游戏公平是薯条哥一直追求的，所以他想让你帮忙测试下这个游戏是否公平。 薯条哥会给出游戏中每个人物的战力 $a_i$，公平的定义是可以将所有人物分成两组，每组都有至少一个人物，且两组的人物战力之和相等。

请你帮忙测试下是否有一种划分方案使得游戏公平。

输入描述

一行，首先输入一个正整数 $n$ 表示游戏人物个数，接下来 $n$ 正整数表示 $n$ 个游戏人物的战力。

$1\leq n\leq 1000, \sum\limits_{i=1}^n a_i\leq 2000$

输出描述

如果有一种方案使得游戏公平，输出1，否则输出0。

样例

输入

7 9 8 2 4 3 5 3

输出

1