// yukicoder: 837 Noelちゃんと星々2 // 2019.6.16 bal4u #include #include #if 1 #define gc() getchar_unlocked() #else #define gc() getchar() #endif int in() // 整数の入力(負数対応) { int n = 0, c = gc(); if (c == '-') { c = gc(); do n = 10*n + (c & 0xf), c = gc(); while (c >= '0'); return -n; } do n = 10*n + (c & 0xf), c = gc(); while (c >= '0'); return n; } int y[100005]; long long s[100005]; int cmp(const void *a, const void *b) { return *(int *)a - *(int *)b; } long long calc(int l, int r) { int m = (l + r) >> 1; if (l == r) return 0; if ((r-l) & 1) return s[r+1] - (s[m+1]<<1) + s[l]; // 偶数 else return s[r+1] - s[m+1] - s[m] + s[l]; // 奇数 } int main() { int i, N; long long a, ans; N = in(); for (i = 0; i < N; i++) y[i] = in(); qsort(y, N, sizeof(int), cmp); if (y[0] == y[N-1]) { puts("1"); return 0; } s[0] = 0; for (i = 0; i < N; i++) s[i+1] = s[i] + y[i]; ans = 0x7fffffffffffffLL; for (i = 1; i < N; i++) { a = calc(0, i-1) + calc(i, N-1); if (a < ans) ans = a; } printf("%lld\n", ans); return 0; }