C# - O(N Log N) Based on Longest Increasing Subsequence
csharp\npublic int KIncreasing(int[] arr, int k)\n{\n\tint count = 0;\n\tList<int>[] current = new List<int>[k];\n\tfor (int i = 0; i < k; i++)\n\t{\n\t\tcurren
```csharp\npublic int KIncreasing(int[] arr, int k)\n{\n\tint count = 0;\n\tList<int>[] current = new List<int>[k];\n\tfor (int i = 0; i < k; i++)\n\t{\n\t\tcurrent[i] = new List<int>();\n\t}\n\n\tfor (int i = 0; i < arr.Length; i++)\n\t{\n\t\tint index = i % k;\n\t\tcurrent[index].Add(arr[i]);\n\t}\n\n\tforeach (var list in current)\n\t{\n\t\tcount += findMin(list);\n\t}\n\n\treturn count;\n}\n\nprivate int findMin(List<int> nums)\n{\n\tint[] d = new int[nums.Count];\n\tint count = 0;\n\n\tforeach (int num in nums)\n\t{\n\t\tint index = Array.BinarySearch(d, 0, count, num);\n\t\tif (index < 0)\n\t\t{\n\t\t\tindex = ~index;\n\t\t}\n\n\t\tif (d[index] == num)\n\t\t{\n\t\t\tindex = Array.BinarySearch(d, 0, count, num + 1);\n\t\t\tif (index < 0)\n\t\t\t{\n\t\t\t\tindex = ~index;\n\t\t\t}\n\t\t}\n\n\t\td[index] = num;\n\t\tif (index == count)\n\t\t{\n\t\t\tcount++;\n\t\t}\n\t}\n\n\treturn nums.Count - count;\n}\n\n\n```
[]