Two-Pan Balance Weighing

You are given a two-pan balance and N weights with weights \(W_{1}, W_{2}, \dots, W_{N}\). Using these weights, you can place any weight on either pan or choose not to use it. Your task is to determine how many different positive weight values can be measured by the balance.

For each weight, you have three choices:

• Place it on the left pan
• Place it on the right pan
• Do not use it

The effective weight measured is the absolute difference between the total weights on the two pans. Note that a measured weight of \(0\) is not considered since it does not correspond to any positive weight measurement.

Input Constraints: The first line contains an integer \(N\). The second line contains \(N\) space-separated integers \(W_1, W_2, \dots, W_N\).

Output: Output a single integer representing the number of different positive weight values that can be measured using the available weights.

inputFormat

The first line contains an integer \(N\), the number of weights. The second line contains \(N\) space-separated integers \(W_1, W_2, \dots, W_N\), where \(W_i\) represents the weight of the \(i\)-th weight.

outputFormat

Output a single integer which is the number of different positive weight values that can be measured.

sample

1
1

1