The mean and the median usually confuse the students because of their similar spelling, but they are quite different concepts. In this problem we are going to work with the mean and the median of a set consisting of N pairwise distinct integers, where N is odd. The mean of such set is defined, as usual, as the sum of the numbers divided by N, while the median is the unique element in the set that is greater than (N-1)/2 of its elements, and less than the other (N-1)/2 elements in the set. For instance, if the set is {0, 2, 6, 4, 13}, then the mean is 5 while the median is 4.

We aim to make student's lives easier by generating "balanced" sets, that is, sets consisting of an odd number of pairwise distinct integers where the mean and the median coincide. For example, the set {0, 2, 6, 4, -2} is balanced, since it has N=5 different integers, and the mean and the median are both equal to 2.

The following procedure has been suggested in order to obtain balanced sets. A set with an even number of distinct integers is chosen, and an extra integer distinct from every element in the set is added to it, in such a way that the resulting set is balanced. We want you to check if the given procedure works. Therefore your task is, given N-1 distinct integers, with odd N, count the number of balanced sets that can be formed by following the described procedure.

Input

The input contains several test cases. Each test case is described with two lines. The first line contains a single odd positive integer N that indicates the number of elements the balanced set must have (3 <= N <= 499). The second line contains N-1 distinct integers Z_i that represent the given elements of the set (-10¹⁴ <= Z_i <= 10¹⁴ for 1 <= i <= N-1). The last line of the input contains the number -1, and should not be processed as a test case.

Output

For each test case, output a single line with an integer representing the total number of different balanced sets that can be obtained by adding an integer to the given set, as explained in the problem description.

Example

Input:

5
0 2 6 4
7
1 2 3 4 5 8
3
-100000000000000 100000000000000
-1

Output:

3
1
3