use std::ops::{Add, Div, Sub}; use proconio::{input, marker::Usize1}; fn solve() -> u64 { input! { n: usize, m: usize, t: u64, a: [Usize1; m], } let mut b = vec![0; n]; for &ai in a.iter() { b[ai] += 1; } binary_search_integer(0, 10u64.pow(18), |x| { let mut ex = 0; let mut em = 0; for &bi in b.iter() { if bi <= x { em += (x - bi) / t; } else { ex += bi - x; } } ex > em }) + 1 } fn main() { let ans = solve(); println!("{}", ans); } fn binary_search_integer(left: T, right: T, pred: impl Fn(T) -> bool) -> T where T: Add + Sub + Div + PartialOrd + From + Copy, { let mut l = left; let mut r = right; while r - l > 1.into() { let m = l + (r - l) / 2.into(); if pred(m) { l = m; } else { r = m; } } l }