[Python] Explanation with pictures, LIS
Given k = 3 for example. Let\'s stay that we start with index = 0, the first condition is A[0] <= A[3], \n\n\nWe also need to guarantee A[3] <= A[6],   A[6] <= 
Given k = 3 for example. Let\'s stay that we start with index = 0, the first condition is **A[0] <= A[3]**, \n![image](https://assets.leetcode.com/users/images/c36a636b-3cf2-4048-b96f-a3ca54bd3b10_1639886464.2410972.png)\n\nWe also need to guarantee **A[3] <= A[6]**,   **A[6] <= A[9]**, etc, if such larger indexs exist. In a word, we need to make this subarray **a = [A[0], A[3], A[6], ... ]** of unique indexes **non-decreasing**.\n![image](https://assets.leetcode.com/users/images/d1441e41-b6b2-4c7c-9208-ed8c8efb7cdd_1639886464.203102.png)\n\n\nThis sub-problem turns into finding the Largest Increasing Subsequence (LIS) of **a**, then the minimum number of changes we shall make equals to **len(a) - LIS(a)**\n\n![image](https://assets.leetcode.com/users/images/ffc17dd6-7b11-4997-a7ab-55d85aa723c3_1639886464.4960089.png)\n\n\nSince the final array is k-increasing, thus we have to compare at most k  subarrays. [A[0], A[k], A[2k], ...], [A[1], A[k + 1], A[2k + 1], ...], ..., [A[k - 1], A[2k - 1], A[3k - 1], ...].\n\nNotice that the changes on one "series" of indexes don\'t interference with other series, so we can safely calculate the number of changes for every series without affecting the answer.\n\nThen the answer is the sum of  **len(a) - LIS(a)** for each subarray.\n\n![image](https://assets.leetcode.com/users/images/cf706ed1-5815-47ae-bcfe-b2d3b1e1af71_1639886464.3358257.png)\n\n**python**\n```\ndef kIncreasing(self, A: List[int], k: int) -> int:\n        def LIS(arr):\n            ans = []\n            for a in arr:\n                idx = bisect.bisect_right(ans, a)\n                if idx == len(ans):\n                    ans.append(a)\n                else:\n                    ans[idx] = a       \n            return len(ans)\n        \n        ans, n = 0, len(A)\n        \n        for start in range(k):\n            cur, idx = [], start\n            while idx < n:\n                cur.append(A[idx])\n                idx += k\n            ans += len(cur) - LIS(cur)\n        return ans\n```
[]