Polycarpus 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

Difficulty: interview

Starter code:

Solutions:
n = int(input())
print(n - 1 if sum(map(int, input().split())) % n else n)

n = int(input())
A=list(map(int,input().split()))
x=0
for i in A:
       x+=i
if not x%n:
    print(n)
else:
    print(n-1)

n = int(input())
arr = list(map(int, input().split()))
sum = 0
for x in arr:
	sum += x
result = n-1
if sum%n == 0:
	result = n
print(result)


import sys
import math
  
n = int(sys.stdin.readline())
an = [int(x) for x in (sys.stdin.readline()).split()]

vsum = sum(an)
if(vsum % n == 0):
    print(int(n))
else:
    print(int(n - 1))

n = int(input())
print(n - (sum(map(int, input().split())) % n != 0))

n = int(input())
a = [int(x) for x in input().split()]
a.sort()
if sum(a) % n == 0:
	print(n)
else:
	print(n - 1)


from math import pi


def main():
    n = int(input())
    s = sum(map(int, input().split()))
    if s % n:
        n -= 1
    print(n)


def __starting_point():
    main()
__starting_point()

a=int(input())
b=sum(map(int,input().split()))
print(a-1 if b%a else a)


x = int(input())
y = list(map(int, input().split(' ')))
tot = sum(y)
mod = tot % x
if mod == 0:
    print(x)
else:
    print(x-1)

n=int(input())
a=[int(v) for v in input().split()]
if sum(a)%n==0:
    print(n)
else:
    print(n-1)

n = int(input())
print(n - 1 if sum(map(int, input().split())) % n else n)


n=int(input())
s=sum(list(map(int, input().split())))+228000*n
print(max(n-s%n, n-1))

n = int(input())
a = list(map(int,input().split()))

s = sum(a)

if s % n == 0 :
    print(n)
else:
    print(n-1)

I=input
n=int(I())
if sum(map(int,I().split()))%n:n-=1
print(n)

n = int(input())

list = input().split()
sum = 0
for i in range(len(list)):
    sum += int(list[i])

if sum % n == 0:
    print(n)
else:
    print(n-1)

import math

n = int(input())
ans = 0

for x in input().split():
    ans += int(x)

if n == 1:
    ans = 1
else:
    if ans == int(ans/n)*n:
        ans = n
    else:
        ans = n-1

print(ans)


import math

n = int(input())
ans = 0

for x in input().split():
    ans += int(x)

if n == 1:
    ans = 1
else:
    if ans == int(ans/n)*n:
        ans = n
    else:
        ans = n-1

print(ans)


n = int(input())
ss = sum(map(int, input().split()))
print(n if ss%n==0 else n-1)


a=int(input())

b=list(map(int,input().split()))

if sum(b)%a!=0:
    print(a-1)
else:
    print(a)


n=int(input())

a=list(map(int,input().split()))

ans=sum(a)

print(n) if ans%n==0 else print(n-1)

'''input
6
-1 1 0 0 -1 -1
'''
n = int(input())
a = list(map(int, input().split()))
print(n if sum(a) % n == 0 else n - 1)

n = int(input())
s = sum([int(i) for i in input().split()])
if s % n == 0:
    print(n)
else:
    print(n - 1)


n=int(input())
a=list(map(int,input().split()))
sum=0
for i in range(n):
    sum+=a[i]
print(n if sum%n==0 else n-1)


n=input()
mas=input()
mas=mas.split(' ',int(len(mas)+1/2))
mas = list(map(int, mas))
k=sum(mas)/len(mas)
if (k%1==0):
    print(len(mas))
else:
    print(len(mas)-1)

n = int(input())
print(n - (sum(map(int, input().split())) % n != 0))