I've been trying to solve this problem for few days now but can't think of a solution.

Here's the statement,

In case you need to read the full statement: Problem Link

What I observed so far:

• worst case is in the form of $$$a^{1} , a^{2} , a^{3} , ... $$$ for some integer $$$a > 1$$$

• in the worst case $$$i$$$ th element has $$$i-1$$$ in degree and $$$n-i$$$ out degree (1 based indexing)

That's all :(

I can't even prove that there's a solution for the worst case. Can someone help me solve this?

Thank you in advance