题目描述

给定正整数 N 和 N 个正偶数 Di 。

在平面直角坐标系中，小麦初始在 (0,0)，每次他可以选取一个未被擦去的 Di ，将其擦去，并从 (x,y) 移动到 (x′ ,y′ ) 使得 ∣x−x′ ∣+∣y−y′∣=Di。

注意，所有坐标都是实数而非整数。例如，Di=2，你可以从 (0,0) 到 (0.85486,1.14514)。

请问经过 N 次移动后，是否可以回到 (0,0)。

如果可以的话，对于所有到达的点 (x,y) 请求出 max(∣x∣+∣y∣) 可能取到的最小值是多少

输入格式

第一行给出数字N

第二个给N个偶数

输出格式

如题所示，如果无解输出-1

输入输出样例 #1

输入 #1

3
2 4 6

输出 #1

4

输入输出样例 #2

输入 #2

5
2 2 2 2 6

输出 #2

3

输入输出样例 #3

输入 #3

2
2 200000

输出 #3

-1

说明/提示

制約

• $1\ \leq\ N\ \leq\ 2\ \times\ 10^5$
• $2\ \leq\ D_i\ \leq\ 2\ \times\ 10^5$