The answer for the problem can be determined within the first $$$4$$$ moves.

Compute $$$f_{j}$$$ as the maximum beauty of the array when Hao chooses index $$$j$$$ as his first move. The answer is then $$$\min\limits_{1\leq j\leq n}(f_{j})$$$.

Read the hints, our goal is to compute $$$f_{j}$$$.

Fix an index $$$i$$$ as Alex's first move (in the second turn), and define:

• $$$l_{1}$$$, $$$l_{2}$$$, and $$$l_{3}$$$ as the indices of the first, second, and third smallest values in the range $$$[1, i-1]$$$.
• $$$r_{1}$$$, $$$r_{2}$$$, and $$$r_{3}$$$ as the indices of the first, second, and third largest values in the range $$$[i+1, n]$$$.

The reason for choosing a triplet will be explained shortly. Let $$$val_{j}$$$ denotes the beauty for index $$$j$$$, defined as $$$val_{j} = a_{i} - a_{j}$$$ for $$$j \lt i$$$ and $$$val_{j} = a_{j} - a_{i}$$$ for $$$i \lt j$$$.

In some cases (such as $$$i = 1$$$), some indices may not exist. However, without loss of generality, assume that all $$$6$$$ indices are valid. Now consider:

These are the $$$6$$$ best choices for Alex in his fourth turn. Before that, Hao has $$$2$$$ turns to eliminate $$$2$$$ numbers. Since he wants to minimize the beauty, he will eliminate the $$$2$$$ largest values.

Sort the above values in descending order. Let $$$x_1$$$, $$$x_{2}$$$, and $$$x_{3}$$$ be the indices corresponding to the $$$3$$$ largest values (where each $$$x_k \in {l_{1}, l_{2}, l_{3}, r_{1}, r_{2}, r_{3}}$$$). The reason for choosing a triplet is to guarantee that $$$x_{1}$$$, $$$x_{2}$$$, and $$$x_{3}$$$ exist.

Let us analyze how this affects $$$f_{j}$$$ by considering $$$j$$$ as Hao's first move.

Case 1: $$$j = i$$$

This is invalid since $$$i$$$ is Alex's first move, so $$$f_{i}$$$ remains unchanged.

Case 2: $$$j = x_{1}$$$ or $$$j = x_{2}$$$

In this case, Hao's first move eliminates either $$$x_{1}$$$ or $$$x_{2}$$$. Therefore, after $$$2$$$ moves (first and third turns), both $$$a_{x_{1}}$$$ and $$$a_{x_{2}}$$$ are eliminated, leaving the maximum beauty for Alex as $$$val_{x_{3}}$$$.

Thus, we update $$$f_{x_{1}} = \max(f_{x_{1}}, val_{x_{3}})$$$ and $$$f_{x_{2}} = \max(f_{x_{2}}, val_{x_{3}})$$$.

Case 3: $$$j \neq i$$$, $$$j \neq x_{1}$$$, and $$$j \neq x_{2}$$$

In this case, Hao's first move does not remove either $$$x_{1}$$$ or $$$x_{2}$$$. Therefore, in his third turn, he will remove $$$x_{1}$$$ since it has the maximum value. Consequently, Alex will select $$$a_{x_{2}}$$$ in his fourth turn, giving a maximum beauty of $$$val_{x_{2}}$$$.

Therefore, we update $$$f_{j} = \max(f_{j}, val_{x_{2}})$$$ for all $$$j$$$ satisfying this case.

I used a Lazy Segment Tree to handle Case 3. If anyone has a more optimal approach, please tell me.

My implementation: 345835104