Pie Chart

Minsik surveyed how many people in each class at his school own dogs. Across the whole school, exactly 100 people own dogs, so if one class has value 15, that class represents 15% of the total.

Minsik wants to make a pie chart from these values. Each class is drawn as one sector whose size is proportional to its value, and the classes may be placed in any order around the circle.

In the pie chart, the boundary between two adjacent sectors is a segment from the center of the circle to the circumference. If two boundaries point in exactly opposite directions, the straight line through them passes through the center and divides the circle into two equal halves. In terms of cumulative percentages around the circle, this happens when two boundary positions differ by 50%.

Minsik wants to choose the order of the classes so that the number of such center-passing lines is as large as possible. Given the number of classes and the value for each class, find the maximum possible number of these lines.

The first line contains the number of classes, N. N is between 1 and 8, inclusive.

The second line contains N integers, the number of dog owners in each class. Each integer is a positive integer not greater than 100, and their sum is always 100.

Output the maximum possible number of lines that pass through the center of the circle.