I was solving this problem Generating sets from the Intel Code Challenge Elimination Round. The editorial doesn't discuss the proof for the idea used. Can anyone help with this? I don't understand the greedy step of why we move the maximum element to the largest possible position.

Also most of the contestants got AC with binary search idea. I considered this idea but couldn't get any head way? I was unable to come up with how to implement a check function which can say whether it is possible to make the maximum $$$\leq x$$$? I read Um_nik's solution and I am unable to figure out why the solution works. Any help is highly appreciated