I have a modification of the Josephus problem (e.g., we have $$$n$$$ people in a circle, and we kick each $$$k$$$-th out till we have only one, tell which number he has), but I have to output the order in which the last $$$4$$$ people (I guess it generalises to $$$p$$$ people in the end) are kicked out.

The constraints are $$$10^7$$$ for both $$$n$$$ and $$$k$$$, which makes it almost impossible to pass a naive solution ($$$O(n \log{k})$$$) without optimisation magic. All Josephus problem approaches which are known to me seem to be ungeneralisable to get the order of elements which are removed from the circle.

Feel free to comment if you have any ideas! The unfolding from the last state (1 element left) doesn't seem to be a very promising strategy, but I might have missed some important observations.