Algorithm for splitting an array into k sub-arrays

We want implement a data structure that have the following methods: Init(A,k)- Gets an array A with n different values and initialize our data structure that so it will divide A into k equally sized sub-arrays (+-1), that each value in the i’th sub-array will be larger than any value in the (i-1)’th sub-array, and smaller than any value in the (i+1)’th sub-array. This method need to be applied in complexity of O(n log k).

Insert(x)- Gets a value x which isn’t in our data structure, and adds it. This method need to be applied in complexity of O(k logn).

I did the init method using Medians- ofMedians QuickSelect, by dividing the array into k’ sub arrays when k’ equals to the closest power of 2 for k, and then I adjusted my pointers to the dividers by using Select on the smaller arrays which added me only O(n).

With the Insert part I’m having some trouble and would appreciate any help, Thanks:)