We use cookies to ensure you have the best browsing experience on our website. Please read our cookie policy for more information about how we use cookies.
  1. Prepare
  2. Algorithms
  3. Dynamic Programming
  4. New Year Present

New Year Present

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.

Input Format

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.

Constraints

Output Format

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

8
4 5 1 5 1 9 4 5

Sample Output 0

3

Sample Input 1

6
1 2 3 4 5 6

Sample Output 1

0

Explanation

Sample 0
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 ).

Sample 1
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 .