class Bit: def __init__(self, n, array=[]): """ :param n: number of elements """ self.n = n self.tree = [0]*(n+1) self.depth = n.bit_length() - 1 for i, a in enumerate(array): self.add(i, a) def get(self,i): """ return summation of elements in [0,i) """ s = 0 i -= 1 while i >= 0: s += self.tree[i] i = (i & (i + 1) )- 1 return s def build(self, array): """ bulid BIT from array """ for i, a in enumerate(array): self.add(i, a) def add(self, i, x): """ add x to i-th element """ while i < self.n: self.tree[i] += x i |= i + 1 def get_range(self,i,j): """ return summation of elements in [i,j) """ if i == 0: return self.get(j) return self.get(j)-self.get(i) def lower_bound(self, x, equal=False): """ return tuple = (return maximum i s.t. a0+a1+...+ai < x (if not existing, -1 ) , a0+a1+...+ai ) if one wants to include equal (i.e., a0+a1+...+ai <= x), please set equal = True (Cation) We must assume that A_i>=0 """ sum_ = 0 pos = -1 # 1-indexed の時は pos = 0 if not equal: for i in range(self.depth, -1, -1): k = pos + (1 << i) if k < self.n and sum_ + self.tree[k] < x: # 1-indexed の時は k <= self.n sum_ += self.tree[k] pos += 1 << i if equal: for i in range(self.depth, -1, -1): k = pos + (1 << i) if k < self.n and sum_ + self.tree[k] <= x: # 1-indexed の時は k <= self.n sum_ += self.tree[k] pos += 1 << i return pos, sum_ def __getitem__(self, i): """ [a0, a1, a2, ...] """ if i<0: i=self.n+i return self.get_range(i,i+1) def __setitem__(self, i, x): self.add(i,x-self[i]) def __iter__(self): """ [a0, a1, a2, ...] """ for i in range(self.n): yield self.get_range(i,i+1) def __str__(self): text1 = " ".join(["element: "] + list(map(str, self))) text2 = " ".join(["cumsum(1-indexed): "]+list(str(self.get(i)) for i in range(1,self.n+1))) return "\n".join((text1, text2)) class SortedList: def __init__(self, n, A=[]): """ :param n: miximum value of A self.size: number of elements in BitSet """ self.n = n self.p = Bit(self.n + 1) self.size = 0 self.flip = 0 self.S = Bit(self.n + 1) for a in A: self.add(a) def add(self,x): self.p.add(x, 1) self.S.add(x, x) self.size += 1 def remove(self,x): self.p.add(x, -1) self.S.add(x, -x) self.size -= 1 def bisect_left(self,x): """ return bisect_left(sorted(B),x) """ if x <= self.n: return self.p.get(x) else: return self.size def bisect_right(self,x): """ return bisect_right(sorted(B),x) """ x += 1 if x <= self.n: return self.p.get(x) else: return self.size def flip_counter(self): return self.flip def count(self,x): return self.p[x] def count_range(self,l,r): """ return number of elements in open set [l,r)""" return self.bisect_left(r)-self.bisect_left(l) def get_range(self,l,r): """ return sum of elements in open set [l,r)""" Sl=self.S.get(l) if r <= self.n: Sr = self.S.get(r) else: Sr = self.S.get(self.n+1) return Sr-Sl def minimum(self,k=1): """ return k-th minimum value """ if k <= self.size: return self.p.lower_bound(k)[0] + 1 else: sys.stderr.write("minimum: list index out of range (k={0})\n".format(k)) def min(self): return self.minimum(1) def max(self): return self.p.lower_bound(self.size)[0] + 1 def upper_bound(self,x,equal=False): """ return maximum element lower than x """ k = self.p.get(x+equal) if k: return self.minimum(k) else: sys.stderr.write("upper_bound: no element smaller than {0} in this BitSet\n".format(x)) def lower_bound(self,x,equal=False): """ return minimum element greater than x """ k =self.p.get(x+1-equal)+1 if k <= self.size: return self.minimum(k) else: sys.stderr.write("lower_bound: no element larger than {0} in this BitSet\n".format(x)) def __getitem__(self, k): """ return k-th minimum element (0-indexed) B[k] = sorted(A)[k] """ if len(self)==0: sys.stderr.write("__getitem__: no elements exist in this BitSet\n") elif k >= len(self): sys.stderr.write("__getitem__: index (={0}) is larger than the maximum index (={1})\n".format(k,len(self)-1)) elif k >= 0: return self.minimum(k+1) else: sys.stderr.write("__getitem__: index (={0}) is negative \n".format(k)) def __len__(self): return self.size def __iter__(self): """ return sorted list """ for i in range(self.n+1): if self.p[i]: for _ in range(self.p[i]): yield i def __str__(self): """ return sorted list """ text1 = " ".join(list(map(str, self))) return "[" + text1 + "]" class SortedList2: """ if we need compress """ def __init__(self, data, A=[]): """ self.size: number of elements in BitSet """ self.data = sorted(list(set(data))) self.n = len(self.data) self.p = Bit(self.n + 1) self.S = Bit(self.n + 1) self.size = 0 self.code = {} self.decode = [] for i, b in enumerate(self.data): self.code[b] = i self.decode.append(b) for a in A: self.add(a) def add(self,x): self.p.add(self.code[x], 1) self.S.add(self.code[x], x) self.size += 1 def remove(self,x): self.p.add(self.code[x], -1) self.S.add(self.code[x], -x) self.size -= 1 def bisect_left(self,x): """ return bisect_left(sorted(B),x) """ if x in self.code.keys(): return self.p.get(self.code[x]) else: return self.p.get(bisect_right(self.data,x)) def bisect_right(self,x): """ return bisect_right(sorted(B),x) """ x += 1 if x in self.code.keys(): return self.p.get(self.code[x]) else: return self.p.get(bisect_right(self.data,x)) def count(self,x): return self.p[self.code[x]] def count_range(self,l,r): """ return number of elements in open set [l,r)""" return self.bisect_left(r)-self.bisect_left(l) def get_range(self,l,r): if l in self.code.keys(): Sl=self.S.get(self.code[l]) else: Sl=self.S.get(bisect_right(self.data,l)) if r in self.code.keys(): Sr=self.S.get(self.code[r]) else: Sr=self.S.get(bisect_right(self.data,r)) return Sr-Sl def minimum(self,k=1): """ return k-th minimum value """ if k <= self.size: return self.decode[self.p.lower_bound(k)[0] + 1] else: sys.stderr.write("minimum: list index out of range (k={0})\n".format(k)) def min(self): return self.minimum(1) def max(self): return self.decode[self.p.lower_bound(self.size)[0] + 1] def upper_bound(self,x,equal=False): """ return maximum element lower than x """ if x in self.code.keys(): y = self.code[x] + equal else: y = bisect_right(self.data, x) k = self.p.get(y) if k: return self.minimum(k) else: sys.stderr.write("upper_bound: no element smaller than {0} in this BitSet\n".format(x)) def lower_bound(self,x,equal=False): """ return minimum element greater than x """ if x in self.code.keys(): y = self.code[x] + 1 - equal else: y = bisect_left(self.data, x) k =self.p.get(y)+1 if k <= self.size: return self.minimum(k) else: sys.stderr.write("lower_bound: no element larger than {0} in this BitSet\n".format(x)) def nearest(self,x,k): """ return k-th nearest value to x """ if k>len(self): sys.stderr.write("nearest: k (= {0}) is larger than the size of this BitSet\n".format(k)) return def test(d): r=self.bisect_right(x+d)-1 l=self.bisect_left(x-d) return r-l+1<=k ok,ng=0,10**18+1 while abs(ok-ng)>1: mid=(ok+ng)//2 if test(mid): ok=mid else: ng=mid d=ok r=self.bisect_right(x+d)-1 l=self.bisect_left(x-d) if d==0: R=self.lower_bound(x,equal=True) L=self.upper_bound(x,equal=True) if abs(x-L)==abs(R-x): if self.count(L)>=k: return L else: return R elif abs(x-L)=len(self)-1: return self[l-1] else: R=self[r+1] L=self[l-1] if abs(x-L)==abs(R-x): if self.count(L)>=k-(r-l+1): return L else: return R elif abs(x-L)= len(self): sys.stderr.write("__getitem__: index (={0}) is larger than the maximum index (={1})\n".format(k,len(self)-1)) elif k >= 0: return self.minimum(k+1) else: sys.stderr.write("__getitem__: index (={0}) is negative \n".format(k)) def __len__(self): return self.size def __iter__(self): """ return sorted list """ for i in range(self.n+1): if self.p[i]: for _ in range(self.p[i]): yield self.decode[i] def __str__(self): """ return sorted list """ text1 = " ".join(list(map(str, self))) return "[" + text1 + "]" ################################################### def example(): global input example = iter( """ 6 10 5 1 5 10 7 """ .strip().split("\n")) input = lambda: next(example) ################################################### import sys input = sys.stdin.readline from bisect import bisect_left, bisect_right # example() N=int(input()) Y=list(map(int, input().split())) Y.sort() if Y[0]==Y[-1]: print(1) exit() A=SortedList2(Y,[]) B=SortedList2(Y,Y) INF=10**10 res=INF for y in Y[:N-1]: A.add(y) B.remove(y) a=A.minimum(len(A)//2+1) la=0 la+=A.count_range(-INF,a)*a-A.get_range(-INF,a) la+=A.get_range(a,INF)-A.count_range(a,INF)*a b=B.minimum(len(B)//2+1) lb=0 lb+=B.count_range(-INF,b)*b-B.get_range(-INF,b) lb+=B.get_range(b,INF)-B.count_range(b,INF)*b res=min(res,la+lb) print(res)