Equal Subset Partition

You are given a list of non-negative integers. Your task is to determine whether the list can be partitioned into two subsets such that the sum of the elements in both subsets is equal.

Formally, given an array a of length n, you need to check if there exists a subset of indices S such that

$$\sum_{i \in S} a_i = \sum_{i \notin S} a_i,$$

which is possible only if the total sum T = \sum_{i=1}^{n} a_i is even. You are required to read the input from stdin and output the result to stdout.

inputFormat

The first line contains an integer n representing the number of elements in the array. The second line contains n space-separated non-negative integers.

Example:

4
1 5 11 5

outputFormat

Output a single line containing either True if the array can be partitioned into two subsets with equal sum or False otherwise.

Example:

True

## sample

4
1 5 11 5

True