Package for this problem was not updated by the problem writer or Codeforces administration after we’ve upgraded the judging servers. To adjust the time limit constraint, solution execution time will be multiplied by 2. For example, if your solution works for 400 ms on judging servers, then value 800 ms will be displayed and used to determine the verdict.

Virtual contest is a way to take part in past contest, as close as possible to participation on time. It is supported only ACM-ICPC mode for virtual contests.
If you've seen these problems, a virtual contest is not for you - solve these problems in the archive.
If you just want to solve some problem from a contest, a virtual contest is not for you - solve this problem in the archive.
Never use someone else's code, read the tutorials or communicate with other person during a virtual contest.

No tag edit access

B. Increase and Decrease

time limit per test

2 secondsmemory limit per test

256 megabytesinput

standard inputoutput

standard outputPolycarpus has an array, consisting of *n* integers *a*_{1}, *a*_{2}, ..., *a*_{n}. Polycarpus likes it when numbers in an array match. That's why he wants the array to have as many equal numbers as possible. For that Polycarpus performs the following operation multiple times:

- he chooses two elements of the array
*a*_{i},*a*_{j}(*i*≠*j*); - he simultaneously increases number
*a*_{i}by 1 and decreases number*a*_{j}by 1, that is, executes*a*_{i}=*a*_{i}+ 1 and*a*_{j}=*a*_{j}- 1.

The given operation changes exactly two distinct array elements. Polycarpus can apply the described operation an infinite number of times.

Now he wants to know what maximum number of equal array elements he can get if he performs an arbitrary number of such operation. Help Polycarpus.

Input

The first line contains integer *n* (1 ≤ *n* ≤ 10^{5}) — the array size. The second line contains space-separated integers *a*_{1}, *a*_{2}, ..., *a*_{n} (|*a*_{i}| ≤ 10^{4}) — the original array.

Output

Print a single integer — the maximum number of equal array elements he can get if he performs an arbitrary number of the given operation.

Examples

Input

2

2 1

Output

1

Input

3

1 4 1

Output

3

Codeforces (c) Copyright 2010-2017 Mike Mirzayanov

The only programming contests Web 2.0 platform

Server time: Mar/26/2017 20:02:08 (c2).

Desktop version, switch to mobile version.
User lists

Name |
---|