#include <bits/stdc++.h>
#pragma GCC optimize("Ofast")
using namespace std;
namespace input {
template <class T>
inline void _R(T& x) {
  cin >> x;
}
inline void R() {}
template <class T1, class... T2>
inline void R(T1& x, T2&... y) {
  _R(x);
  R(y...);
}
}  // namespace input
using namespace input;
namespace overload_output {
template <class T1, class T2>
inline ostream& operator<<(ostream& out, pair<T1, T2>& p) {
  return out << p.first << ' ' << p.second;
}
template <class T>
inline ostream& operator<<(ostream& out, vector<T>& x) {
  for (auto i : x) out << i << ' ';
  return out;
}
template <class T>
inline ostream& operator<<(ostream& out, deque<T>& x) {
  for (auto i : x) out << i << ' ';
  return out;
}
template <class T>
inline ostream& operator<<(ostream& out, forward_list<T>& x) {
  for (auto i : x) out << i << ' ';
  return out;
}
template <class T>
inline ostream& operator<<(ostream& out, list<T>& x) {
  for (auto i : x) out << i << ' ';
  return out;
}
template <class T>
inline ostream& operator<<(ostream& out, set<T>& x) {
  for (auto i : x) out << i << ' ';
  return out;
}
template <class T>
inline ostream& operator<<(ostream& out, multiset<T>& x) {
  for (auto i : x) out << i << ' ';
  return out;
}
template <class T>
inline ostream& operator<<(ostream& out, unordered_set<T>& x) {
  for (auto i : x) out << i << ' ';
  return out;
}
template <class T>
inline ostream& operator<<(ostream& out, unordered_multiset<T>& x) {
  for (auto i : x) out << i << ' ';
  return out;
}
template <class T1, class T2>
inline ostream& operator<<(ostream& out, map<T1, T2>& x) {
  for (auto i : x) out << i << ' ';
  return out;
}
template <class T1, class T2>
inline ostream& operator<<(ostream& out, multimap<T1, T2>& x) {
  for (auto i : x) out << i << ' ';
  return out;
}
template <class T1, class T2>
inline ostream& operator<<(ostream& out, unordered_map<T1, T2>& x) {
  for (auto i : x) out << i << ' ';
  return out;
}
template <class T1, class T2>
inline ostream& operator<<(ostream& out, unordered_multimap<T1, T2>& x) {
  for (auto i : x) out << i << ' ';
  return out;
}
}  // namespace overload_output
using namespace overload_output;
namespace output {
template <class T>
inline void _W(const T& x) {
  cout << x;
}
template <class T1, class T2>
inline void _W(const pair<T1, T2>& p) {
  _W(p.first);
  _W(' ');
  _W(p.second);
}
template <class T>
inline void _W(const vector<T>& x) {
  bool isFirst = 1;
  for (auto i : x) {
    if (!isFirst) cout << ' ';
    isFirst = 0;
    cout << i;
  }
}
template <class T>
inline void _W(const deque<T>& x) {
  bool isFirst = 1;
  for (auto i : x) {
    if (!isFirst) cout << ' ';
    isFirst = 0;
    cout << i;
  }
}
template <class T>
inline void _W(const forward_list<T>& x) {
  bool isFirst = 1;
  for (auto i : x) {
    if (!isFirst) cout << ' ';
    isFirst = 0;
    cout << i;
  }
}
template <class T>
inline void _W(const list<T>& x) {
  bool isFirst = 1;
  for (auto i : x) {
    if (!isFirst) cout << ' ';
    isFirst = 0;
    cout << i;
  }
}
template <class T1, class T2, class T3>
inline void _W(const set<T1, T2, T3>& x) {
  bool isFirst = 1;
  for (auto i : x) {
    if (!isFirst) cout << ' ';
    isFirst = 0;
    cout << i;
  }
}
template <class T>
inline void _W(const multiset<T>& x) {
  bool isFirst = 1;
  for (auto i : x) {
    if (!isFirst) cout << ' ';
    isFirst = 0;
    cout << i;
  }
}
template <class T>
inline void _W(const unordered_set<T>& x) {
  bool isFirst = 1;
  for (auto i : x) {
    if (!isFirst) cout << ' ';
    isFirst = 0;
    cout << i;
  }
}
template <class T>
inline void _W(const unordered_multiset<T>& x) {
  bool isFirst = 1;
  for (auto i : x) {
    if (!isFirst) cout << ' ';
    isFirst = 0;
    cout << i;
  }
}
template <class T1, class T2>
inline void _W(const map<T1, T2>& x) {
  bool isFirst = 1;
  for (auto i : x) {
    if (!isFirst) cout << ' ';
    isFirst = 0;
    cout << i;
  }
}
template <class T1, class T2>
inline void _W(const multimap<T1, T2>& x) {
  bool isFirst = 1;
  for (auto i : x) {
    if (!isFirst) cout << ' ';
    isFirst = 0;
    cout << i;
  }
}
template <class T1, class T2>
inline void _W(const unordered_map<T1, T2>& x) {
  bool isFirst = 1;
  for (auto i : x) {
    if (!isFirst) cout << ' ';
    isFirst = 0;
    cout << i;
  }
}
template <class T1, class T2>
inline void _W(const unordered_multimap<T1, T2>& x) {
  bool isFirst = 1;
  for (auto i : x) {
    if (!isFirst) cout << ' ';
    isFirst = 0;
    cout << i;
  }
}
inline void W() { cout << '\n'; }
template <class T>
inline void W(const T& x) {
  _W(x);
  W();
}
template <class T1, class... T2>
inline void W(const T1& x, const T2&... y) {
  _W(x);
  _W(' ');
  W(y...);
}
}  // namespace output
using namespace output;
int main() {
  int n;
  R(n);
  int sum = 0;
  for (int i = 0; i < n; i++) {
    int x;
    R(x);
    sum += x;
  }
  if (sum % n == 0)
    W(n);
  else
    W(n - 1);
  return 0;
}
static auto _batch_ios = []() {
  ios::sync_with_stdio(false);
  cin.tie(0);
  cout << fixed << setprecision(12);
  return 42;
}();

### Prompt

Your challenge is to write a cpp solution to the following problem:

Polycarpus has an array, consisting of n integers a1, a2, ..., an. 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 ai, aj (i ≠ j); 
  * he simultaneously increases number ai by 1 and decreases number aj by 1, that is, executes ai = ai + 1 and aj = aj - 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 ≤ 105) — the array size. The second line contains space-separated integers a1, a2, ..., an (|ai| ≤ 104) — 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

### Response

```cpp
#include <bits/stdc++.h>
#pragma GCC optimize("Ofast")
using namespace std;
namespace input {
template <class T>
inline void _R(T& x) {
  cin >> x;
}
inline void R() {}
template <class T1, class... T2>
inline void R(T1& x, T2&... y) {
  _R(x);
  R(y...);
}
}  // namespace input
using namespace input;
namespace overload_output {
template <class T1, class T2>
inline ostream& operator<<(ostream& out, pair<T1, T2>& p) {
  return out << p.first << ' ' << p.second;
}
template <class T>
inline ostream& operator<<(ostream& out, vector<T>& x) {
  for (auto i : x) out << i << ' ';
  return out;
}
template <class T>
inline ostream& operator<<(ostream& out, deque<T>& x) {
  for (auto i : x) out << i << ' ';
  return out;
}
template <class T>
inline ostream& operator<<(ostream& out, forward_list<T>& x) {
  for (auto i : x) out << i << ' ';
  return out;
}
template <class T>
inline ostream& operator<<(ostream& out, list<T>& x) {
  for (auto i : x) out << i << ' ';
  return out;
}
template <class T>
inline ostream& operator<<(ostream& out, set<T>& x) {
  for (auto i : x) out << i << ' ';
  return out;
}
template <class T>
inline ostream& operator<<(ostream& out, multiset<T>& x) {
  for (auto i : x) out << i << ' ';
  return out;
}
template <class T>
inline ostream& operator<<(ostream& out, unordered_set<T>& x) {
  for (auto i : x) out << i << ' ';
  return out;
}
template <class T>
inline ostream& operator<<(ostream& out, unordered_multiset<T>& x) {
  for (auto i : x) out << i << ' ';
  return out;
}
template <class T1, class T2>
inline ostream& operator<<(ostream& out, map<T1, T2>& x) {
  for (auto i : x) out << i << ' ';
  return out;
}
template <class T1, class T2>
inline ostream& operator<<(ostream& out, multimap<T1, T2>& x) {
  for (auto i : x) out << i << ' ';
  return out;
}
template <class T1, class T2>
inline ostream& operator<<(ostream& out, unordered_map<T1, T2>& x) {
  for (auto i : x) out << i << ' ';
  return out;
}
template <class T1, class T2>
inline ostream& operator<<(ostream& out, unordered_multimap<T1, T2>& x) {
  for (auto i : x) out << i << ' ';
  return out;
}
}  // namespace overload_output
using namespace overload_output;
namespace output {
template <class T>
inline void _W(const T& x) {
  cout << x;
}
template <class T1, class T2>
inline void _W(const pair<T1, T2>& p) {
  _W(p.first);
  _W(' ');
  _W(p.second);
}
template <class T>
inline void _W(const vector<T>& x) {
  bool isFirst = 1;
  for (auto i : x) {
    if (!isFirst) cout << ' ';
    isFirst = 0;
    cout << i;
  }
}
template <class T>
inline void _W(const deque<T>& x) {
  bool isFirst = 1;
  for (auto i : x) {
    if (!isFirst) cout << ' ';
    isFirst = 0;
    cout << i;
  }
}
template <class T>
inline void _W(const forward_list<T>& x) {
  bool isFirst = 1;
  for (auto i : x) {
    if (!isFirst) cout << ' ';
    isFirst = 0;
    cout << i;
  }
}
template <class T>
inline void _W(const list<T>& x) {
  bool isFirst = 1;
  for (auto i : x) {
    if (!isFirst) cout << ' ';
    isFirst = 0;
    cout << i;
  }
}
template <class T1, class T2, class T3>
inline void _W(const set<T1, T2, T3>& x) {
  bool isFirst = 1;
  for (auto i : x) {
    if (!isFirst) cout << ' ';
    isFirst = 0;
    cout << i;
  }
}
template <class T>
inline void _W(const multiset<T>& x) {
  bool isFirst = 1;
  for (auto i : x) {
    if (!isFirst) cout << ' ';
    isFirst = 0;
    cout << i;
  }
}
template <class T>
inline void _W(const unordered_set<T>& x) {
  bool isFirst = 1;
  for (auto i : x) {
    if (!isFirst) cout << ' ';
    isFirst = 0;
    cout << i;
  }
}
template <class T>
inline void _W(const unordered_multiset<T>& x) {
  bool isFirst = 1;
  for (auto i : x) {
    if (!isFirst) cout << ' ';
    isFirst = 0;
    cout << i;
  }
}
template <class T1, class T2>
inline void _W(const map<T1, T2>& x) {
  bool isFirst = 1;
  for (auto i : x) {
    if (!isFirst) cout << ' ';
    isFirst = 0;
    cout << i;
  }
}
template <class T1, class T2>
inline void _W(const multimap<T1, T2>& x) {
  bool isFirst = 1;
  for (auto i : x) {
    if (!isFirst) cout << ' ';
    isFirst = 0;
    cout << i;
  }
}
template <class T1, class T2>
inline void _W(const unordered_map<T1, T2>& x) {
  bool isFirst = 1;
  for (auto i : x) {
    if (!isFirst) cout << ' ';
    isFirst = 0;
    cout << i;
  }
}
template <class T1, class T2>
inline void _W(const unordered_multimap<T1, T2>& x) {
  bool isFirst = 1;
  for (auto i : x) {
    if (!isFirst) cout << ' ';
    isFirst = 0;
    cout << i;
  }
}
inline void W() { cout << '\n'; }
template <class T>
inline void W(const T& x) {
  _W(x);
  W();
}
template <class T1, class... T2>
inline void W(const T1& x, const T2&... y) {
  _W(x);
  _W(' ');
  W(y...);
}
}  // namespace output
using namespace output;
int main() {
  int n;
  R(n);
  int sum = 0;
  for (int i = 0; i < n; i++) {
    int x;
    R(x);
    sum += x;
  }
  if (sum % n == 0)
    W(n);
  else
    W(n - 1);
  return 0;
}
static auto _batch_ios = []() {
  ios::sync_with_stdio(false);
  cin.tie(0);
  cout << fixed << setprecision(12);
  return 42;
}();

```