I have an alternate solution for D2. Sort the array, place the first half on odd indices and second half on even indices. For example if the sorted array is 2,4,6,8,10; then make the array as 6,2,8,4,10. After this, count the number of elements which are less than their neighbours. If there are repeated elements, it would still be a valid arrangement to find maximal no. of cheap spheres.

This is in a way similar to your solution, where I am using the same concept that if we can find x cheap, we can definitely find x-1 cheap spheres too. By this method, you can directly get the maximum amount of cheap spheres possible.

problems aren't visible.. lol