Nina received an odd New Year's present from a student: a set of unbreakable sticks. Each stick has a length, , and the length of the stick is . Deciding to turn the gift into a lesson, Nina asks her students the following:
How many ways can you build a square using exactly of these unbreakable sticks?
Note: Two ways are distinct if they use at least one different stick. As there are choices of sticks, we must determine which combinations of sticks can build a square.
The first line contains an integer, , denoting the number of sticks. The second line contains space-separated integers describing the length of each stick in the set.
On a single line, print an integer representing the number of ways that unbreakable sticks can be used to make a square.
Sample Input 0
4 5 1 5 1 9 4 5
Sample Output 0
Sample Input 1
1 2 3 4 5 6
Sample Output 1
Given sticks (), the only possible side length for our square is . We can build square in different ways:
In order to build a square with side length using exactly sticks, and must always build two of the sides. For the remaining two sides, you must choose of the remaining sticks of length ( and ).
We have to use all sticks, making the largest stick length () the minimum side length for our square. No combination of the remaining sticks can build more sides of length (total length of all other sticks is and we need at least length ), so we print .