You are given a binary array \(A\) with elements \(0\) and \(1\) of size \(N\), and integer \(K\). Let's call the score of an array the difference between the maximum and minimum element within the array. For example \([1,0,0,1,0,0]\), the Score of this given array is \(1-0 = 1\).
Now you have to partition the array into \(K\) continuous subarrays such that the summation of the score of all the subarrays is minimum. You also have to output starting and ending points of the subarrays corresponding to the minimum score, in increasing order of starting point. If there are multiple possibilities then output the subarrays such that starting points will be lexicographically smallest.
Input format
Output format
Constraints
\(A = [0, 0, 1, 0, 1]\), \(K = 2\)
Possible partitions:
So minimum possible score is \(1\) and lexicographically smallest starting points subarrays will be \([0],[0,1,0,1]\).