EQUI - Equilibrium

Original statement in spanish at http://www.dc.uba.ar/events/icpc/download/problems/taip2011-problems.pdf

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 (-1014 <= Z_i <= 1014 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

Added by:Pablo Ariel Heiber
Date:2011-10-04
Time limit:1.046s
Source limit:50000B
Memory limit:1536MB
Cluster: Cube (Intel G860)
Languages:All except: ASM64
Resource:Argentinian Programming Tournament 2011

hide comments
2018-11-17 04:06:53
The inputs are not necessarily in ascending order.
2016-04-24 22:21:13 Abhishek jaiswal
my 100 th :)
2012-08-09 22:14:06 seshank
answers can be 0,1,2,3 only

Last edit: 2012-08-09 22:14:51
2012-07-21 09:29:23 rit
My code is working correct for all test case but show wrong answer. Any one plzzz help!!!
2011-11-01 13:16:43 cegprakash
could someone tell what are the three balanced sets possible for first test case?
i can see only one possible way :(
2011-10-21 13:58:17 albertg
Nice problem.
© Spoj.com. All Rights Reserved. Spoj uses Sphere Engine™ © by Sphere Research Labs.