Migrated from Lutece 3006 平等云雾

All parts of this problem, including description, images, samples, data and checker, might be broken. If you find bugs in this problem, please contact the admins.

Description

波波和他的老师都很公平，因此他们一起玩了一个名叫“平等云雾”的游戏。 这个游戏需要一副 $n$ 张牌的牌堆，每张卡牌具有一个点数。对于每张卡牌，波波需要把这张牌分给自己或者老师。由于波波和老师都很喜爱公平，因此他们希望所有卡牌分完之后波波拥有的卡牌点数之和与老师拥有的卡牌点数之和的差的绝对值尽可能小。 同时，波波还拥有无数张加倍卡，一张加倍卡可以使一张卡牌的点数翻倍。注意：一张卡牌只能享受一张加倍卡的加成，无法多次加倍。 现在，波波和他的老师想要知道双方点数之差绝对值的可能最小值是多少，你能告诉他们吗？

Input

第一行一个整数 $n$ ，表示卡牌的数量 第二行共 $n$ 个整数，其中第 $i$ 个整数 $a_i$ 表示每张卡牌的点数

Output

输出一个整数，表示双方点数之差绝对值的可能最小值

Samples

3
6 5 3

1

Constraints

$1 \leq n \leq 100$ $1 \leq a_i \leq 100$

Note

一张卡牌只能享受一张加倍卡的加成，无法多次加倍

Resources

2023 UESTC ICPC Training for Search and Dynamic Programming