import bisect class segt: def __init__(self, n, ele, calc): self.num = 2 ** (n - 1).bit_length() self.el = ele self.data = [ele] * (2 * self.num) self.calc = calc def update(self, idx, x): idx += self.num - 1 self.data[idx] = x while idx > 0: idx = (idx - 1) // 2 self.data[idx] = self.calc(self.data[2*idx+1], self.data[2*idx+2]) def renew(self, idx, x): self.update(idx, self.calc(self.get(idx), x)) def prod(self, left, right): l = left + self.num r = right + self.num res = self.el while l < r: if l % 2: res = self.calc(res, self.data[l-1]) l += 1 if r % 2: r -= 1 res = self.calc(res, self.data[r-1]) l //= 2 r //= 2 return res def get(self, idx): return self.data[idx+self.num-1] def add(x, y): return x + y def solve(n, k, d, h): sorted_h = sorted(list(set(h))) st = segt(n, 0, add) cnt = segt(n, 0, add) di = dict() di_inv = dict() for v in sorted_h: di[v] = len(di) di_inv[di[v]] = v # print(di) for v in h[:k]: st.renew(di[v], v) cnt.renew(di[v], 1) ans = 1 << 60 for i in range(n-k+1): l, r = -1, (1 << 30) - 1 while r - l > 1: piv = (l + r) // 2 x = bisect.bisect_right(sorted_h, piv) y = bisect.bisect_right(sorted_h, piv+d) # print(piv, u, x) if cnt.prod(0, x) > cnt.prod(y, n): r = piv else: l = piv # print(l, r) x = bisect.bisect_right(sorted_h, r) y = bisect.bisect_right(sorted_h, r+d) res = (cnt.prod(0, x) * r - st.prod(0, x)) + (st.prod(y, n) - (r+d) * cnt.prod(y, n)) # print((r, r+d), (x, y), res) # print((cnt.prod(0, x), cnt.prod(y, n))) ans = min(ans, res) if i < n - k: st.renew(di[h[i]], -h[i]) cnt.renew(di[h[i]], -1) st.renew(di[h[i+k]], h[i+k]) cnt.renew(di[h[i+k]], 1) return ans def naive(n, k, d, h): ans = 1 << 60 for i in range(n-k+1): ls = h[i:i+k] for x in range(min(ls), max(ls)+1): res = 0 for v in ls: if v < x: res += x - v if x + d < v: res += v - (x + d) # if res == 1: # print(ls, x) ans = min(ans, res) return ans n, k, d = map(int, input().split()) h = list(map(int, input().split())) print(solve(n, k, d, h)) # print(naive(n, k, d, h)) exit() import random n = 5 for _ in range(200): k = random.randint(2, n) d = random.randint(0, 10) h = [random.randint(0, 10) for _ in range(n)] try: solve(n, k, d, h) except: print(n, k, d) print(*h) assert 0 break if solve(n, k, d, h) != naive(n, k, d, h): print(n, k, d) print(*h) break