题解 | #数组分组#

# 其实递归的想法很单纯，但是就是会超时，优化了好久最后发现一开始做所有输入数字之和的奇偶判断可以省很多时间
# 本来想看题解，还是强行自己优化出来了，6
import sys

ipt = []

for line in sys.stdin:
    nums = list(map(int, line.strip().split()))

    ipt.append(nums)

nums = ipt[1]

three, five, other = [], [], []

# print(nums, three, five, other)

for num in nums:
    if num % 3 == 0:
        three.append(num)
    elif num % 5 == 0:
        five.append(num)
    else:
        other.append(num)

three, five = sum(three), sum(five)

other.sort() if other else None

# print(nums, three, five, other)

def judge(three, five, other):
    other_set = list(set(other))
    # print(three, five, other_set)
    if other:
        if three == five and sum(other) == 0:
            return True
        elif three == five and sum(other) != 0:
            return False
        elif three != five and (three + sum(other) == five or five + sum(other) == three):
            return True
        for i in range(len(other_set)):
            # print(i, other[i], three, five)
            another = other[:]
            c = another.pop(i)
            if i > 0 and other[i-1] == c:
                continue
            res = judge(three+c, five, another) or judge(three, five+c, another)
            if res:
                return True
        
    else:
        if three == five:
            return True
        else:
            return False

if (three + five + sum(other)) % 2 != 0:
    res = False
else:
    res = judge(three, five, other)

# print(res, 1)

if res:
    print('true')
else:
    print('false')