fn calc_val(y: &Vec, start_idx: usize, count: usize) -> usize { let base_val: usize = (2*start_idx + count - 1) / 2; let base_val: isize = y[base_val]; y.iter().skip(start_idx).take(count) .map(|i| (i - base_val).abs() as usize) .sum() } fn calc(y: &Vec, split_idx: usize) -> usize { calc_val(y, 0, split_idx) + calc_val(y, split_idx, y.len() - split_idx) } fn main() { let mut n = String::new(); std::io::stdin().read_line(&mut n).ok(); let n: usize = n.trim().parse().unwrap(); let mut y = String::new(); std::io::stdin().read_line(&mut y).ok(); let mut y: Vec = y.trim().split_whitespace().map(|s| s.parse().unwrap()).collect(); y.sort(); if y[0] == y[n-1] { println!("{}", 1); return; } let mut left: usize = 1; let mut right: usize = n; while right - left > 3 { let mleft = (2*left + right) / 3; let mright = (left + 2*right) / 3; let ll = calc(&y, left); let ml = calc(&y, mleft); let mr = calc(&y, mright); let rr = calc(&y, right); let minval = vec![ll, ml, mr, rr].into_iter().min().unwrap(); if ll == minval { right = mleft; } else if rr == minval { left = mright; } else if ml == minval { right = mright; } else { left = mleft; } } let mleft = (2*left + right) / 3; let mright = (left + 2*right) / 3; let ll = calc(&y, left); let ml = calc(&y, mleft); let mr = calc(&y, mright); let rr = calc(&y, right); println!("{}", vec![ll, ml, mr, rr].iter().min().unwrap()); }