In the pattern introduction, the complexity analysis is pretty hand-wavy in that it vaguely refers to the inverse ackerman function and offers nothing further.

Then, in this problem somehow that odd time complexity from the introduction turns into n log n. It is not obvious to me how this works. The explanation is pretty minimal.