金克丝（Jinx）和蔚（Vi）正在挑选队员，以便为上城（Topside）与祖安（Zaun）之间注定的决战组建两支最公平的队伍。

目前，有 $N$ 个尚未决定为哪一方效力的候选人。每个人都有一个代表其能力的实力值 $a_i$。

虽然金克丝和蔚通常会想为自己的一方挑选最强的战士，但为了提高他们热门剧集《双城之战》（Arcane）的收视率，他们决定组建两支势均力敌的队伍。因此，他们制定了以下几条限制规则：

1. 每支队伍的人数必须相等。
2. 因为一个人不能同时为双方效力，所以每个人最多只能成为其中一支队伍的成员。
3. 两支队伍的实力值之和必须相等。
4. 队伍的人数（即每队的人数）必须尽可能大。否则，每个战士就无法获得良好的角色成长（character development）。

他们想知道满足 these 条件的队伍的最大人数，如果不存在这样的队伍，则输出 $-1$。你能帮帮他们吗？

输入格式

输入的第一行包含一个整数 $N$ ($1 \le N \le 300$)，表示尚未决定阵营的人数。

第二行包含 $N$ 个空格分隔的整数 $a_1, \dots, a_N$ ($1 \le a_i \le 300$)，表示每个人的实力值。

输出格式

输出一行，包含一个整数，表示最大队伍人数 $S$。如果无法组建满足条件的队伍，则输出 $-1$。

样例

输入格式 1

6
1 1 4 1 2 3

输出格式 1

3