import bisect n = int(input()) a = list(map(int, input().split())) a.sort() prefix_sum = [0] * (n + 1) for i in range(n): prefix_sum[i+1] = prefix_sum[i] + a[i] max_s = -float('inf') for j in range(n): aj = a[j] # Calculate L: number of elements <= aj L = bisect.bisect_right(a, aj) # Calculate R: number of elements > aj R = n - bisect.bisect_right(a, aj) t_max = min(L - 1, R) if t_max < 0: continue # Calculate sum_small: sum of the largest t_max elements <= aj (excluding aj itself) start_small = L - 1 - t_max if start_small < 0: sum_small = prefix_sum[L-1] else: sum_small = prefix_sum[L-1] - prefix_sum[start_small] # Calculate sum_large: sum of the largest t_max elements > aj sum_large = prefix_sum[n] - prefix_sum[n - t_max] s = sum_small + sum_large - 2 * t_max * aj if s > max_s: max_s = s print(max_s)