def main(): import sys input = sys.stdin.read data = input().split() N = int(data[0]) a = list(map(int, data[1:N+1])) a.sort() # Compute prefix sums prefix = [0] * (N + 1) for i in range(N): prefix[i+1] = prefix[i] + a[i] # Compute suffix sums suffix = [0] * (N + 1) for i in range(1, N+1): suffix[i] = suffix[i-1] + a[N - i] max_S = -float('inf') for k in range(1, N+1): if k % 2 == 1: # Odd m = (k - 1) // 2 t = k - (m + 1) if t < 0: t = 0 sum_subset = prefix[m+1] + suffix[t] median = a[m] else: # Even m = (k // 2) - 1 t = k - (m + 1) if t < 0: t = 0 sum_subset = prefix[m+1] + suffix[t] # The median is (a[m] + a[n - t]) / 2 median = (a[m] + a[N - t]) / 2 S = sum_subset - k * median if S > max_S: max_S = S print(int(max_S)) if __name__ == '__main__': main()