컨테이너 재배치

항구의 컨테이너 하치장 바닥에는 컨테이너를 쌓을 수 있는 칸이 일렬로 총 $n$개 그려져 있고, 현재 하치장에는 총 $m$개의 컨테이너가 쌓여 있다. 컨테이너의 높이는 모두 1로 같으며, 각 칸에 쌓을 수 있는 컨테이너 수에는 제한이 없다. $a_i$ ($1 ≤ i ≤ n$)를 $i$번째 칸에 쌓인 컨테이너 수라고 하면 $m = \sum_{i=1}^{n} a_i$가 성립한다.

높이에 제한이 없어 칸마다 쌓인 컨테이너 수의 차이가 크면 안전상 문제가 생길 수 있다. 그래서 크레인으로 일부 컨테이너를 다른 칸으로 옮겨, 어떤 두 칸의 높이 차이도 1 이하가 되도록 재배치하려고 한다. 즉, 임의의 $i$, $j$에 대해 $|a_i - a_j| ≤ 1$이 만족되어야 한다. 컨테이너는 한 번에 한 개씩만 옮길 수 있으며, 옮기는 거리에 따른 추가 비용은 없다.

예를 들어 그림 1처럼 35개의 컨테이너가 8개의 칸에 쌓여 있으면 $m = 35$, $n = 8$이다. 높이 차이가 1 이하가 되도록 재배치하면 그림 2와 같은 결과가 나오며, 이때 컨테이너 5개를 옮겨야 한다.

그림 1. 재배치 이전	그림 2. 재배치 결과

첫 번째 줄에 컨테이너를 쌓을 수 있는 칸의 개수를 나타내는 양의 정수 $n$ ($1 ≤ n ≤ 10^6$)이 주어진다. 다음 줄에는 현재 각 칸에 쌓여 있는 컨테이너 수 $a_i$를 나타내는 0 이상의 정수 $n$개가 주어진다. 컨테이너의 총 개수 $m$은 $1 ≤ m ≤ 2 \times 10^9$을 만족한다.

임의의 $i$, $j$에 대해 $|a_i - a_j| ≤ 1$ 조건을 만족하기 위해 옮겨야 하는 컨테이너의 최소 개수를 한 줄에 출력한다.