Two-Pan Balance

Interview

Time limit1sMemory limit512 MB

Summary

Given up to 13 distinct weights, count how many integers from 1 to their sum cannot be formed when each weight goes on the bowl side, the other pan, or unused.

Level: Medium6 of 10
Topics: Brute force, Backtracking, Math, Bit manipulation
Solved: No attempts yet

Problem

There are k weights of distinct masses and an empty bowl. Every weight has an integer mass, and the bowl is taken to have mass 0. You want to put a desired amount of water into the bowl using a two-pan balance exactly once. Let S be the sum of the masses of all the given weights. For example, if there are 3 weights with masses {1, 2, 6}, then S = 9, and using the balance exactly once you can put amounts of water corresponding to every integer from 1 to S into the bowl as follows. Here X is the mass of the water put into the bowl, and □ is the bowl.

X	1	2	3	4	5	6	7	8	9
	□:1	□:2	□:(1+2)	(□+2):6	(□+1):6	□:6	□:(1+6)	□:(2+6)	□:(1+2+6)

If the weights are {1, 5, 7}, then S = 13, and the masses you can put into the bowl using the balance exactly once are {1, 2, 3, 4, 5, 6, 7, 8, 11, 12, 13}. That is, among the numbers from 1 to S, you cannot put amounts of water corresponding to 9 and 10 into the bowl.

Given the masses g1, g2, ..., gk of k weights (3 ≤ k ≤ 13), write a program that finds how many integers from 1 to S cannot be measured using the two-pan balance exactly once.

Input

The first line gives the integer k (3 ≤ k ≤ 13), the number of weights. The next line gives k integers gi (1 ≤ gi ≤ 200,000) separated by spaces, which are the masses of the weights.

Output

Print how many integers from 1 to S, where S is the sum of the weights' masses, cannot be measured using the two-pan balance exactly once.

Examples1

Example 1
Input
```
3
1 5 7
```
Expected output
```
2
```