a few solutions
This problem is 300. Longest Increasing Subsequence in disguise, ie. for each kth "bucket" from 0..K-1 inclusive, we accumulate the LIS, then subtract the accum
This problem is [300. Longest Increasing Subsequence](https://leetcode.com/problems/longest-increasing-subsequence/discuss/385203/The-ART-of-Dynamic-Programming) in disguise, ie. for each `k`<sup>th</sup> "bucket" from `0..K-1` inclusive, we accumulate the [LIS](https://leetcode.com/problems/longest-increasing-subsequence/discuss/385203/The-ART-of-Dynamic-Programming), then subtract the accumulated [LIS](https://leetcode.com/problems/longest-increasing-subsequence/discuss/385203/The-ART-of-Dynamic-Programming) from `N` (the cardinality of the input array `A`) as the minimum "cost" we pay to make all `k` "buckets" monotonically increasing.\n\nThe reason we need to use a monotonic stack `S` is because N = 1e5, and thus we need a near-linear O(N * logN) solution to avoid TLE.  To calculate the [LIS](https://leetcode.com/problems/longest-increasing-subsequence/discuss/385203/The-ART-of-Dynamic-Programming) we initialize the monotonic stack `S` to the first element of the current `k`<sup>th</sup> bucket under consideration.  Then for each subsequent value `x` from `bucket[k][1..n-1]` (where `n` is the length of each `k`<sup>th</sup> bucket, ie. `n = N / K`), we have two choices to consider:\n\n1. \u2705 `x` **can** be appended onto the monotonic stack `S` without violating the monotonically increasing constraint\n2. \uD83D\uDEAB `x` **cannot** be appended onto the monotonic stack `S` without violating the monotonically increasing constraint\n\n* When case 1 occurs, we simply append `x` onto the monotonic stack `S`.  \n* When case 2 occurs, we would usually pop from the monotonic stack until the monotonically increasing constraint is met by `x`, then append `x` onto `S`.  However for finding the [LIS](https://leetcode.com/problems/longest-increasing-subsequence/discuss/385203/The-ART-of-Dynamic-Programming) in O(N * logN) time, we set `S[i] = x`, where `i` is the upper bound index of `x` in `S`.\n\n**Credit:** [votrubac\'s Q4 solution in Contest 272: 2111. Minimum Operations to Make the Array K-Increasing](https://leetcode.com/problems/minimum-operations-to-make-the-array-k-increasing/discuss/1634969/LIS-in-Disguise)\n* This is an awesome way to find the LIS in near-linear time, ie. O(N * logN) \uD83C\uDF89\n\n---\n\n*Kotlin*\n```\nclass Solution {\n    fun upperBound(A: MutableList<Int>, T: Int): Int {\n        var N = A.size\n        var (i, j) = Pair(0, N - 1)\n        while (i < j) {\n            var k = (i + j) / 2\n            if (A[k] <= T)\n                i = k + 1\n            else\n                j = k\n        }\n        return i\n    }\n    fun kIncreasing(A: IntArray, K: Int): Int {\n        var N = A.size\n        fun LIS(A: MutableList<Int>): Int {\n            var S = mutableListOf<Int>(A[0])\n            for (x in A.slice(1..A.lastIndex)) {\n                if (S.last() <= x) {\n                    S.add(x)\n                } else {\n                    var i = upperBound(S, x)\n                    S[i] = x\n                }\n            }\n            return S.size\n        }\n        var bucket = Array(K){ mutableListOf<Int>() }\n        for (k in 0 until K)\n            for (i in k until N step K)\n                bucket[k].add(A[i])\n        return N - IntArray(K){ LIS(bucket[it]) }.sum()!!\n    }\n}\n```\n\n*Javascript*\n```\nlet kIncreasing = (A, K, N = A.length, bucket = [...Array(K)].map(_ => [])) => {\n    let LIS = A => {\n        let S = [A[0]];\n        for (let x of A.slice(1)) {\n            if (S[S.length - 1] <= x) {\n                S.push(x);\n            } else {\n                let i = _.sortedLastIndex(S, x);\n                S[i] = x;\n            }\n        }\n        return S.length;\n    };\n    for (let k = 0; k < K; ++k)\n        for (let i = k; i < N; i += K)\n            bucket[k].push(A[i]);\n    return N - _.sum([...Array(K).keys()].map(k => LIS(bucket[k])));\n};\n```\n\n*Python3*\n```\nclass Solution:\n    def kIncreasing(self, A: List[int], K: int) -> int:\n        N = len(A)\n        def LIS(A):\n            S = [A[0]]\n            for x in A[1:]:\n                if S[-1] <= x:\n                    S.append(x)\n                else:\n                    i = bisect_right(S, x)\n                    S[i] = x\n            return len(S)\n        return N - sum(LIS(A[i::K]) for i in range(K))\n```\n\n*C++*\n```\nclass Solution {\npublic:\n    using VI = vector<int>;\n    using VVI = vector<VI>;\n    int kIncreasing(VI& A, int K, int cost = 0) {\n        int N = A.size();\n        auto LIS = [&](auto& A) {\n            VI S{ A[0] };\n            for (auto x: VI{ A.begin() + 1, A.end() }) {\n                if (S.back() <= x) {\n                    S.push_back(x);\n                } else {\n                    auto i = distance(S.begin(), upper_bound(S.begin(), S.end(), x));\n                    S[i] = x;\n                }\n            }\n            return S.size();\n        };\n        VVI bucket(K);\n        for (auto k{ 0 }; k < K; ++k)\n            for (auto i{ k }; i < N; i += K)\n                bucket[k].push_back(A[i]);\n        for (auto k{ 0 }; k < K; ++k)\n            cost += LIS(bucket[k]);\n        return N - cost;\n    }\n};\n```
[]