#pragma GCC target ("avx") #pragma GCC optimize("Ofast") #pragma GCC optimize("unroll-loops") //#pragma GCC target("sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx,avx,tune=native") #define _USE_MATH_DEFINES #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include using namespace std; using ll = long long; using ld = long double; using H = pair; using P = pair; using vi = vector; #define all(a) (a).begin(),(a).end() #define fs first #define sc second #define xx first #define yy second.first #define zz second.second #define Q(i,j,k) mkp(i,mkp(j,k)) #define rng(i,s,n) for(ll i = (s) ; i < (n) ; i++) #define rep(i,n) rng(i, 0, (n)) #define mkp make_pair #define vec vector #define pb emplace_back #define siz(a) (int)(a).size() #define crdcomp(b) sort(all((b)));(b).erase(unique(all((b))),(b).end()) #define getidx(b,i) (lower_bound(all(b),(i))-(b).begin()) #define ssp(i,n) (i==(ll)(n)-1?"\n":" ") #define ctoi(c) (int)(c-'0') #define itoc(c) (char)(c+'0') #define cyes printf("Yes\n") #define cno printf("No\n") #define cdf(n) for(int quetimes_=(n);quetimes_>0;quetimes_--) #define gcj printf("Case #%lld: ",qq123_+1) #define readv(a,n) a.resize(n,0);rep(i,(n)) a[i]=read() #define found(a,x) (a.find(x)!=a.end()) constexpr ll mod = (ll)1e9 + 7; constexpr ll Mod = 998244353; constexpr ld EPS = 1e-10; constexpr ll inf = (ll)3 * 1e18; constexpr int Inf = (ll)15 * 1e8; constexpr int dx[] = { -1,1,0,0 }, dy[] = { 0,0,-1,1 }; templatebool chmax(T& a, const T& b) { if (a < b) { a = b; return 1; } return 0; } templatebool chmin(T& a, const T& b) { if (b < a) { a = b; return 1; } return 0; } ll read() { ll u, k = scanf("%lld", &u); return u; } string reads() { string s; cin >> s; return s; } H readh(short g = 0) { H u; int k = scanf("%lld %lld", &u.fs, &u.sc); if (g == 1) u.fs--, u.sc--; if (g == 2) u.fs--; return u; } bool ina(H t, int h, int w) { return 0 <= t.fs && t.fs < h && 0 <= t.sc && t.sc < w; } bool ina(int t, int l, int r) { return l <= t && t < r; } ll gcd(ll i, ll j) { return j ? gcd(j, i % j) : i; } ll popcount(ll x) { int sum = 0; for (int i = 0; i < 60; i++)if ((1ll << i) & x) sum++; return sum; } template class csum { vec v; public: csum(vec& a) :v(a) { build(); } csum() {} void init(vec& a) { v = a; build(); } void build() { for (int i = 1; i < v.size(); i++) v[i] += v[i - 1]; } //[l,r] T a(int l, int r) { if (r < l) return 0; return v[r] - (l == 0 ? 0 : v[l - 1]); } //[l,r) T b(int l, int r) { return a(l, r - 1); } T a(pairt) { return a(t.first, t.second); } T b(pairt) { return b(t.first, t.second); } }; class mint { public:ll v; mint(ll v = 0) { s(v % mod + mod); } constexpr static int mod = Mod;// (ll)1e9 + 7; constexpr static int fn_ = (ll)2e6 + 5; static mint fact[fn_], comp[fn_]; mint pow(int x) const { mint b(v), c(1); while (x) { if (x & 1) c *= b; b *= b; x >>= 1; } return c; } inline mint& s(int vv) { v = vv < mod ? vv : vv - mod; return *this; } inline mint inv()const { return pow(mod - 2); } inline mint operator-()const { return mint() - *this; } inline mint& operator+=(const mint b) { return s(v + b.v); } inline mint& operator-=(const mint b) { return s(v + mod - b.v); } inline mint& operator*=(const mint b) { v = v * b.v % mod; return *this; } inline mint& operator/=(const mint b) { v = v * b.inv().v % mod; return *this; } inline mint operator+(const mint b) const { return mint(v) += b; } inline mint operator-(const mint b) const { return mint(v) -= b; } inline mint operator*(const mint b) const { return mint(v) *= b; } inline mint operator/(const mint b) const { return mint(v) /= b; } friend ostream& operator<<(ostream& os, const mint& m) { return os << m.v; } friend istream& operator>>(istream& is, mint& m) { int x; is >> x; m = mint(x); return is; } bool operator<(const mint& r)const { return v < r.v; } bool operator>(const mint& r)const { return v > r.v; } bool operator<=(const mint& r)const { return v <= r.v; } bool operator>=(const mint& r)const { return v >= r.v; } bool operator==(const mint& r)const { return v == r.v; } bool operator!=(const mint& r)const { return v != r.v; } explicit operator bool()const { return v; } explicit operator int()const { return v; } mint comb(mint k) { if (k > * this) return mint(); if (!fact[0]) combinit(); if (v >= fn_) { if (k > * this - k) k = *this - k; mint tmp(1); for (int i = v; i >= v - k.v + 1; i--) tmp *= mint(i); return tmp * comp[k.v]; } return fact[v] * comp[k.v] * comp[v - k.v]; }//nCk mint perm(mint k) { if (k > * this) return mint(); if (!fact[0]) combinit(); if (v >= fn_) { mint tmp(1); for (int i = v; i >= v - k.v + 1; i--) tmp *= mint(i); return tmp; } return fact[v] * comp[v - k.v]; }//nPk static void combinit() { fact[0] = 1; for (int i = 1; i < fn_; i++) fact[i] = fact[i - 1] * mint(i); comp[fn_ - 1] = fact[fn_ - 1].inv(); for (int i = fn_ - 2; i >= 0; i--) comp[i] = comp[i + 1] * mint(i + 1); } }; mint mint::fact[fn_], mint::comp[fn_]; //-------------------------------------------------------------- //-------------------------------------------------------------- template class LazySegmentTree { protected: using UPF = function; using QRF = function; using F = function; using ll = long long; int n, rr; vectordat; vectorlen; LazySegmentTree() {} LazySegmentTree(int size) { init(size); } LazySegmentTree(vector& v) { init(v); } virtual ~LazySegmentTree() {} virtual void eval(const T& par, T& a, const int& al) = 0; virtual void fold(T& par, const int& pl) = 0; virtual T proc(const T& a, const int& al, const T& b, const int& bl) = 0; public: void init(int size) { n = size, rr = 1; while (rr < n) rr <<= 1; dat.assign(2 * rr - 1, T()); len.assign(2 * rr - 1, 0); for (int i = 0; i < n; i++) { len[i + rr - 1] = 1; dat[i + rr - 1] = T(); } for (int i = rr - 2; i >= 0; i--) { len[i] = len[i * 2 + 1] + len[i * 2 + 2]; dat[i] = proc(dat[i * 2 + 1], len[i * 2 + 1], dat[i * 2 + 2], len[i * 2 + 2]); } } void init(vector& v) { n = (int)v.size(), rr = 1; while (rr < n) rr <<= 1; dat.assign(2 * rr - 1, T()); len.assign(2 * rr - 1, 0); for (int i = 0; i < n; i++) { dat[i + rr - 1] = v[i]; len[i + rr - 1] = 1; } for (int i = rr - 2; i >= 0; i--) { len[i] = len[i * 2 + 1] + len[i * 2 + 2]; dat[i] = proc(dat[i * 2 + 1], len[i * 2 + 1], dat[i * 2 + 2], len[i * 2 + 2]); } } //one point update void set(int at, T x) { update(0, at, at + 1, 0, rr, [x](T& a) {a = x; }); } void upd(int a, int b, UPF func) { upd(0, a, b, 0, rr, func); } T qry(int a, int b) { return qry(0, a, b, 0, rr); } T get0() { return dat[0]; } //func([a,i))==true, func([a,i+1))==false int lb(int a, int b, F func) { T e = T(); int lgt = 0; return lb(0, a, b, 0, rr, func, e, lgt); } //func([i,b))==true, func([i-1,b))==false int ub(int a, int b, F func) { T e = T(); int lgt = 0; return ub(0, a, b, 0, rr, func, e, lgt); } private: void upd(int i, const int& a, const int& b, int l, int r, UPF& func) { if (b <= l || r <= a) return; if (a <= l && r <= b) { func(dat[i], len[i]); return; } eval(dat[i], dat[i * 2 + 1], len[i * 2 + 1]); eval(dat[i], dat[i * 2 + 2], len[i * 2 + 2]); fold(dat[i], len[i]); upd(i * 2 + 1, a, b, l, (l + r) / 2, func); upd(i * 2 + 2, a, b, (l + r) / 2, r, func); dat[i] = proc(dat[i * 2 + 1], len[i * 2 + 1], dat[i * 2 + 2], len[i * 2 + 2]); } T qry(int i, const int& a, const int& b, int l, int r) { if (b <= l || r <= a) return T(); if (a <= l && r <= b) return dat[i]; eval(dat[i], dat[i * 2 + 1], len[i * 2 + 1]); eval(dat[i], dat[i * 2 + 2], len[i * 2 + 2]); fold(dat[i], len[i]); return proc(qry(i * 2 + 1, a, b, l, (l + r) / 2), len[i * 2 + 1], qry(i * 2 + 2, a, b, (l + r) / 2, r), len[i * 2 + 2]); } int lb(int i, int a, int b, int l, int r, F& func, T& wa, int& lgt) { if (b <= l || r <= a) return b; if (a <= l && r <= b) { if (func(proc(wa, lgt, dat[i], len[i]))) { wa = proc(wa, lgt, dat[i], len[i]); lgt += len[i]; return b; } if (r - l == 1) return l; } eval(dat[i], dat[i * 2 + 1], len[i * 2 + 1]); eval(dat[i], dat[i * 2 + 2], len[i * 2 + 2]); fold(dat[i], len[i]); int tmp = lb(i * 2 + 1, a, b, l, (l + r) / 2, func, wa, lgt); if (tmp < b) return tmp; return lb(i * 2 + 2, a, b, (l + r) / 2, r, func, wa, lgt); } int ub(int i, int a, int b, int l, int r, F& func, T& wa, int& lgt) { if (b <= l || r <= a) return a; if (a <= l && r <= b) { if (func(proc(dat[i], len[i], wa, lgt))) { wa = proc(dat[i], len[i], wa, lgt); lgt += len[i]; return a; } if (r - l == 1) return r; } eval(dat[i], dat[i * 2 + 1], len[i * 2 + 1]); eval(dat[i], dat[i * 2 + 2], len[i * 2 + 2]); fold(dat[i], len[i]); int tmp = ub(i * 2 + 2, a, b, (l + r) / 2, r, func, wa, lgt); if (tmp > a) return tmp; return ub(i * 2 + 1, a, b, l, (l + r) / 2, func, wa, lgt); } }; template class Segtree :public LazySegmentTree { using Base = LazySegmentTree; public: Segtree() {} Segtree(int size) { init(size); } Segtree(vector& v) { init(v); } void init(int size) { Base::init(size); } void init(vector& v) { vectorr(v.size()); for (int i = 0; i < v.size(); i++) r[i] = v[i]; Base::init(r); } void update(int a, int b, ll x) { Base::upd(a, b, [x](T& dat, const int& len) { dat += x; }); } ll query(int a, int b) { return Base::qry(a, b); } ll get0() { return Base::get0(); } private: void eval(const T& par, T& a, const int& al)override { } void fold(T& par, const int& pl) override { } T proc(const T& a, const int& al, const T& b, const int& bl)override { return a + b; } }; template class sptable { using F = function; vectorv; vector>dat; vectorlog; F func; public: sptable(F func) :func(func) {} sptable(vectora, F func) :func(func) { init(a); } void init(vectora) { v = a; int n = a.size(); log.assign(n + 1, 0); for (int i = 1; i <= n; i++) log[i] = log[i >> 1] + 1; dat.assign(log[n], vector(n)); for (int i = 0; i < n; i++) dat[0][i] = i; for (int i = 1; i < log[n]; i++) { for (int j = 0; j < n - (1 << i) + 1; j++) { int c = dat[i - 1][j]; int d = dat[i - 1][j + (1 << (i - 1))]; dat[i][j] = (func(a[c], a[d]) == a[c] ? c : d); } } } int idx_get(int l, int r) { int pos = log[r - l] - 1; int c = dat[pos][l]; int d = dat[pos][r - (1 << pos)]; return (func(v[c], v[d]) == v[c] ? c : d); } T get(int l, int r) { return v[idx_get(l, r)]; } T operator()(int l, int r) const { return get(l, r); } }; int n, k; vi a; signed main() { cin >> n >> k; readv(a, n); if (k == 1) { cout << a[0] << endl; return 0; } vi b = a; crdcomp(b); Segtree cnt(siz(b)), val(siz(b)); sptablespt(a, [](ll a, ll b) {return min(a, b); }); ll ans = a[k - 1]; for (int i = n - 1; i >= k - 1; i--) { int tmp = getidx(b, a[i]); int r = (i + k - 2) / (k - 1); if (!(r * k-1 <= n && i+1<=n)) { cnt.update(tmp, tmp + 1, 1); val.update(tmp, tmp + 1, a[i]); continue; } int pos = cnt.lb(0, siz(b), [&r](ll a) {return a < r - 1; }) + 1; ll sum = a[i] + val.query(0, pos) - (cnt.query(0, pos) - (r - 1)) * b[pos - 1]; //k*r >= を1つ使う if (spt.get(k * r - 1, n) == spt.get(i + 1, n)) { chmin(ans, sum); } else { chmin(ans, sum - b[pos - 1] + spt.get(k * r - 1, n)); } cnt.update(tmp, tmp + 1, 1); val.update(tmp, tmp + 1, a[i]); } cout << ans << endl; }