Alice and Bob play a game with an integer array nums, with Alice taking the first turn.

On each turn, the current player must choose and remove a non empty prefix or suffix of the array such that the remaining array is non empty. The game concludes when exactly $1$ element remains.

Alice aims to maximize the value of the final element, whereas Bob aims to minimize it. Assuming both players play optimally, return the value of the final remaining element.

Constraints:

• $1 \leq$ nums.length $\leq 10^5$

• $1 \leq$ nums[i] $\leq 10^5$

Now, let’s take a moment to make sure you’ve correctly understood the problem. The quiz below helps you check if you’re solving the correct problem:

We have a game for you to play. Rearrange the logical building blocks to develop a clearer understanding of how to solve this problem.

Implement your solution in the following coding playground.