Final element after subarray deletions

impl Solution {
  pub fn final_element(nums: Vec<i32>) -> i32 {
    // Key insight: each turn removes a subarray of size < current length,
    // meaning at least 1 element and at most m-1 elements.
    // After removal, elements on both sides are concatenated.
    //
    // Think about it: with array of size m, player removes subarray of size 1..m-1.
    // The remaining has size 1..m-1. So each turn reduces the array.
    //
    // For n=1: answer is nums[0]
    // For n=2: Alice moves first, removes 1 element (subarray of size 1 < 2).
    //          Alice wants to maximize, so removes the smaller one. Answer = max.
    // For n=3: Alice removes subarray of size 1 or 2.
    //   If Alice removes 1 element, array becomes size 2, Bob picks max of remaining 2? No, Bob minimizes.
    //   Bob with size 2: removes 1 element, wants to minimize, removes the larger one. Answer = min of remaining 2.
    //   If Alice removes 2 elements (contiguous subarray), array becomes size 1. That's the answer directly.
    //   Alice can remove any subarray of size 2: [0..1], [1..2]. Remaining would be nums[2] or nums[0].
    //   So Alice can pick max(nums[0], nums[2]) directly, or leave 2 elements for Bob.
    //   If Alice removes 1 element: she can remove nums[0] leaving [nums[1],nums[2]],
    //     Bob takes max of those, answer = min(nums[1],nums[2])
    //   Or remove nums[1] (subarray [1..1]) leaving [nums[0],nums[2]], Bob takes max, answer = min(nums[0],nums[2])
    //   Or remove nums[2] leaving [nums[0],nums[1]], answer = min(nums[0],nums[1])
    //   Or remove subarray of size 2: [0..1] leaving nums[2], or [1..2] leaving nums[0].
    //
    //   For [1,5,2]: Alice options:
    //     Remove size 2: leave nums[2]=2 or nums[0]=1. Best = 2.
    //     Remove size 1: leave 2 elements, Bob minimizes by removing larger, leaving smaller.
    //       Remove nums[0]=1: left [5,2], Bob removes 5, answer=2
    //       Remove nums[1]=5: left [1,2], Bob removes 2, answer=1
    //       Remove nums[2]=2: left [1,5], Bob removes 5, answer=1
    //     Best from size 1 removal: 2. Best from size 2 removal: 2. Answer = 2.
    //
    // Pattern analysis: Let's sort and think about it.
    // n=1: answer = nums[0] (the only element)
    // n=2: answer = max (Alice picks)
    // n=3: answer = median (second largest)
    //
    // Let me think more carefully. With n elements, the game takes n-1 turns total
    // (each turn removes at least 1 element, game ends at 1 element).
    // Actually no - a turn can remove more than 1 element.
    //
    // The key insight: the player can remove any contiguous subarray of size 1 to m-1.
    // Since they can remove a subarray of size 1, each player can always just remove
    // a single element. But they can also remove larger subarrays.
    //
    // Let's think about what the final element can be. The final element must be one of
    // the original elements.
    //
    // Actually, let me think about this differently. The game ends when 1 element remains.
    // The total number of "turns" depends on how many elements are removed each turn.
    //
    // With optimal play, let's think about sorted array.
    // Let sorted = sort(nums).
    // n=1: sorted[0]
    // n=2: sorted[1] (max)
    // n=3: sorted[1] (median). For [1,5,2] sorted=[1,2,5], answer=2=sorted[1].
    //
    // Hypothesis: answer = median = sorted[(n-1)/2]?
    // For n=2: sorted[0]? No, answer is sorted[1]. (n-1)/2 = 0. Wrong.
    //
    // Let me reconsider. For n=2, Alice goes first and wants max. She removes 1 element
    // (must be subarray of size < 2, i.e. size 1). She removes the min. Answer = max = sorted[1].
    //
    // For n=3, we showed answer = sorted[1] (the median).
    // For n=4: let's think. sorted = [a,b,c,d].
    //   Alice can remove 1,2, or 3 elements.
    //   If she removes 3 (subarray of size 3), she leaves 1 element. She'd pick d.
    //   But wait, it must be a contiguous subarray. She can only remove a contiguous subarray of size 3.
    //   For a sorted array that's [a,b,c] or [b,c,d]. Leaving d or a. Alice picks to leave d.
    //   But the array isn't necessarily sorted! The elements are in original order.
    //
    //   Hmm, the contiguity constraint matters. Alice can remove any contiguous subarray of
    //   size up to m-1. With size 4, she can remove up to 3 contiguous elements.
    //   Removing 3 contiguous elements from size 4 leaves either the first or last element.
    //   So Alice can choose max(nums[0], nums[n-1]).
    //
    //   Actually for n=4, Alice can also remove subarrays of other sizes.
    //   But she can get max(first, last) in one move, ending the game. That's powerful.
    //   However Bob then... wait, if Alice removes 3 elements from a 4-element array,
    //   only 1 element remains and game ends. So Alice has full control.
    //   Answer for n=4 = max(nums[0], nums[n-1]).
    //
    //   Wait that doesn't seem right either. Let me reconsider n=4 with [1,2,3,4].
    //   Alice removes subarray of size 3: removes [1,2,3] leaving [4], or [2,3,4] leaving [1].
    //   Alice picks [4]. Answer = 4 = max.
    //
    //   What about [2,4,1,3]? Alice removes [2,4,1] leaving [3], or [4,1,3] leaving [2].
    //   Or removes size 2: [2,4] leaving [1,3], [4,1] leaving [2,3], [1,3] leaving [2,4].
    //   Or removes size 1: leaving 3 elements for Bob.
    //
    //   If Alice removes [2,4,1] → answer 3.
    //   If Alice removes [4,1,3] → answer 2.
    //   If Alice removes [2,4] → [1,3], Bob's turn with n=2, Bob wants min, removes 3, answer=1. Bad for Alice.
    //   If Alice removes [4,1] → [2,3], Bob removes 3, answer=2.
    //   If Alice removes [1,3] → [2,4], Bob removes 4, answer=2.
    //   If Alice removes size 1:
    //     Remove [2] → [4,1,3], Bob with n=3. Bob wants to minimize.
    //       Bob can remove 2 contiguous → [4,1] leaving [3], or [1,3] leaving [4], or remove 1 → leaves 2 for Alice.
    //       Bob minimizes: remove [1,3] leaving [4]? No, Bob wants min. Remove [4,1] leaving 3. Or remove [4] → [1,3], Alice removes 1, answer 3. Or remove [1] → [4,3], Alice removes min(4,3)=3? No Alice wants max, removes 3? No, Alice removes the one she doesn't want. Alice with [4,3] removes 3, answer 4.
    //       Bob with [4,1,3]: to minimize, Bob removes subarray of size 2: [4,1]→[3] (answer 3), [1,3]→[4] (answer 4). Or size 1: remove [4]→[1,3] Alice gets 3. remove [1]→[4,3] Alice gets 4. remove [3]→[4,1] Alice gets 4.
    //       Bob's best: remove [4,1] leaving answer 3. Or remove [4] leaving [1,3] Alice gets 3. Min is 3.
    //     Remove [4] → [2,1,3], Bob with n=3.
    //       Bob: remove size 2: [2,1]→[3], [1,3]→[2]. Size 1: [2]→[1,3] Alice→3. [1]→[2,3] Alice→3. [3]→[2,1] Alice→2.
    //       Bob's best: [1,3]→[2], answer 2. Or [3]→[2,1] Alice→2. Min = 2.
    //     Remove [1] → [2,4,3], Bob with n=3.
    //       Bob: size 2: [2,4]→[3], [4,3]→[2]. Size 1: [2]→[4,3] Alice→4. [4]→[2,3] Alice→3. [3]→[2,4] Alice→4.
    //       Bob's best: [4,3]→[2], answer 2. Min = 2.
    //     Remove [3] → [2,4,1], Bob with n=3.
    //       Bob: size 2: [2,4]→[1], [4,1]→[2]. Size 1: [2]→[4,1] Alice→4. [4]→[2,1] Alice→2. [1]→[2,4] Alice→4.
    //       Bob's best: [2,4]→[1], answer 1.
    //
    //   Alice's best options: remove 3 contiguous → answer 3.
    //   From size-1 removals: best is removing [2] → answer 3.
    //   So answer for [2,4,1,3] = 3.
    //   Sorted: [1,2,3,4]. Answer = 3 = sorted[2].
    //   max(first,last) = max(2,3) = 3. That also works here.
    //
    // Hmm let me reconsider. For even n, Alice can remove n-1 elements in one go
    // (a contiguous subarray of size n-1), leaving either first or last element.
    // answer >= max(nums[0], nums[n-1]).
    // Can she do better? She could remove fewer, but then Bob gets a turn.
    //
    // For odd n >= 3:
    //   Alice removes some subarray, Bob plays on result.
    //   If n=3: we showed answer = median when sorted.
    //
    // Actually let me think about this more carefully with the observation that
    // removing a contiguous subarray of size m-1 from array of size m leaves
    // either the first or last element.
    //
    // n=1: trivially nums[0].
    // n=2: Alice removes 1, leaves max(first, last).
    // n=3: Alice can leave to Bob a 2-element array, or end in 1.
    //   If end in 1: remove 2 contiguous, leave first or last.
    //   If leave 2 for Bob: Bob will keep max of those 2? No, Bob wants min, so Bob removes
    //   larger, leaving smaller. So outcome = min of those 2.
    //   Alice compares: max(first,last) vs best of (min of some pair).
    //   For [1,5,2]: max(first,last)=max(1,2)=2. Or leave 2 for Bob... Alice removes 1 element (contiguous subarray of size 1), leaving 2 adjacent elements. The remaining pairs: remove first→[5,2] Bob keeps 2, remove middle→[1,2] Bob keeps 1, remove last→[1,5] Bob keeps 1.
    //   Best for Alice from 2-element: max(2,1,1)=2. Best from 1-element: max(1,2)=2. Answer=2.
    //
    // For n=5: Alice goes first on odd array.
    //   She can remove 4 contiguous → leave first or last.
    //   Or leave something for Bob.
    //
    // I think the answer is: sort the array, answer = sorted[n/2] (0-indexed, integer division).
    // n=1: sorted[0]. n=2: sorted[1]. n=3: sorted[1]. n=4: sorted[2].
    // For [2,4,1,3]: sorted=[1,2,3,4], sorted[2]=3. ✓
    // For [1,5,2]: sorted=[1,2,5], sorted[1]=2. ✓
    // For [3,7]: sorted=[3,7], sorted[1]=7. ✓
    //
    // Let me verify with n=5, [1,2,3,4,5]. Hypothesis: sorted[2]=3.
    // Alice can remove 4 contiguous: leave first=1 or last=5.
    // But 5>3, so if Alice can get 5, she'd prefer that. Unless Bob can counter...
    // Wait, Alice removes 4 elements leaving 1. No more turns. Answer = 5 if she removes [1,2,3,4].
    // That contradicts sorted[2]=3.
    //
    // So my hypothesis is wrong. Let me reconsider.
    //
    // For n=5 [1,2,3,4,5]: Alice removes [1,2,3,4] (size 4 < 5). Leaves [5]. Answer = 5.
    // So answer = 5 = max.
    //
    // Hmm. For odd n, Alice can end the game immediately by removing n-1 elements.
    // She'd leave max(first, last).
    //
    // For even n, Alice removes 1..n-1 elements. If she removes n-1 (odd number check:
    // subarray of size n-1 from array of size n), she leaves first or last.
    // But then it's done. Wait, for n=3 she can also do this!
    //
    // For n=3, [1,5,2]: Alice removes [1,5] (size 2 subarray), leaves [2].
    // Or removes [5,2] leaves [1]. Best = max(2,1) = 2.
    // But the max element is 5. She can't leave 5 because 5 is in the middle.
    // She can only leave first or last by removing n-1 contiguous elements.
    //
    // Can she remove just 1 element to leave [1,2] or [5,2] or [1,5] for Bob?
    // Bob with [1,5]: removes [1], leaves 5? No Bob wants min. Bob removes [5], leaves 1.
    // Bob with [5,2]: Bob removes [5], leaves 2.
    // Bob with [1,2]: Bob removes [2], leaves 1.
    //
    // So from removing 1 element: best outcome for Alice is 2 (remove first, Bob gets [5,2]→2).
    // From removing 2 elements: best is max(first,last) = max(1,2) = 2.
    // Overall answer = 2.
    //
    // For [1,2,3,4,5]: Alice removes [1,2,3,4] → leaves 5. Done. Answer = 5.
    // Interesting. So for odd n, the answer is max(first, last)?
    //
    // [5,1,2,3,4]: Alice removes [1,2,3,4] → leaves 5. Answer = 5.
    // [3,1,5,2,4]: Alice removes [3,1,5,2] → 4, or [1,5,2,4] → 3. max(3,4) = 4.
    // But could she do better? Remove [3] → [1,5,2,4] (n=4, Bob's turn).
    //   Bob with [1,5,2,4] (even n=4): Bob can remove 3 contiguous → leave first=1 or last=4.
    //   Bob wants min → leaves 1. Outcome 1. Bad for Alice.
    //   Bob could also remove fewer. But Bob can guarantee leaving 1.
    // Remove [1] → [3,5,2,4] Bob can leave 3 or 4. Bob picks 3.
    // Remove [5] → [3,1,2,4] Bob can leave 3 or 4. Bob picks 3.
    // Remove [2] → [3,1,5,4] Bob can leave 3 or 4. Bob picks 3.
    // Remove [4] → [3,1,5,2] Bob can leave 3 or 2. Bob picks 2.
    // Remove [3,1] → [5,2,4] (n=3, Bob's turn, odd). Bob can remove 2 → leave first=5 or last=4. Bob picks min = 4. But can Bob do worse? Bob removes [5] → [2,4] Alice gets 4. Bob removes [2] → [5,4] Alice gets 5. Bob removes [4] → [5,2] Alice gets 5. Bob removes [5,2] → [4]. Bob removes [2,4] → [5].
    // Bob's best with [5,2,4]: remove [5,2] → [4], answer 4. Or remove [2] → [5,4] Alice→5. Hmm Bob wants min.
    // Bob options: remove 2 contiguous → leave 5 or 4. min(5,4)=4. Or remove 1 → leave 2 for Alice (Alice picks max). [5]→[2,4] Alice→4. [2]→[5,4] Alice→5. [4]→[5,2] Alice→5. Bob's best from 1 removal: 4. So Bob gets 4 either way.
    //
    // For Alice with [3,1,5,2,4]: removing [3,1] → Bob gets [5,2,4] → 4.
    // Remove [1,5] → [3,2,4], Bob's turn (n=3, odd). Bob: remove 2→ leave 3 or 4, min=3. Remove 1: [3]→[2,4] Alice→4, [2]→[3,4] Alice→4, [4]→[3,2] Alice→3. Bob best = 3.
    // Remove [5,2] → [3,1,4], Bob (n=3). Bob: remove 2 → leave 3 or 4, min=3. Bob best = 3.
    // Remove [2,4] → [3,1,5], Bob (n=3). remove 2 → leave 3 or 5, min=3. Best=3.
    // Remove [3,1,5] → [2,4], Bob (n=2). Bob removes 4, answer=2.
    // Remove [1,5,2] → [3,4], Bob (n=2). Bob removes 4, answer=3.
    // Remove [5,2,4] → [3,1], Bob (n=2). Bob removes 3, answer=1.
    // Remove [3,1,5,2] → [4], answer=4.
    // Remove [1,5,2,4] → [3], answer=3.
    //
    // Alice's best: max of all options = 4 (from removing [3,1,5,2] or from removing [3,1] where Bob gets 4).
    //
    // For [3,1,5,2,4]: sorted = [1,2,3,4,5]. Answer = 4.
    // max(first,last) = max(3,4) = 4. ✓
    //
    // Let me check another: [2,5,1,4,3]. max(first,last) = max(2,3) = 3.
    // Alice removes [2,5,1,4] → [3], answer 3.
    // Alice removes [5,1,4,3] → [2], answer 2.
    // Alice removes [2,5,1] → [4,3], Bob → 3.
    // Can Alice get > 3? Remove [2] → [5,1,4,3], Bob (n=4 even).
    //   Bob removes 3 contiguous from [5,1,4,3]: [5,1,4]→[3], [1,4,3]→[5]. Bob picks 3.
    //   But Bob could also: remove [5]→[1,4,3] Alice(n=3,odd) gets max(1,3)=3. remove [1]→[5,4,3] Alice gets max(5,3)=5. Bob won't do that. remove [4]→[5,1,3] Alice gets max(5,3)=5. remove [3]→[5,1,4] Alice gets max(5,4)=5.
    //   Bob removes [5,1]→[4,3] Alice→4. Remove [1,4]→[5,3] Alice→5. Bob won't. Remove [4,3]→[5,1] Alice→5.
    //   Bob's best with [5,1,4,3]: remove [5,1,4]→3. Or remove [5]→[1,4,3] Alice gets max(1,3)=3. Both give 3.
    //   So Alice removing [2] → 3.
    // Seems like answer = 3 = max(first, last) for this case too.
    //
    // New hypothesis for odd n: answer = max(first, last).
    // For even n: after Alice's move, Bob faces some array.
    //
    // For even n=2: Alice(maximizer) → answer = max.
    // For even n=4: Alice removes contiguous subarray of size 1..3.
    //   If size 3: leaves first or last → max(first,last). Game ends.
    //   If size 1 or 2: Bob gets array of size 2 or 3.
    //
    // Wait, for even n=4, Alice goes first.
    // Alice can immediately end: remove 3 contiguous → max(first, last).
    // Or remove fewer for potentially better outcome.
    //
    // [1,4,2,3]: Alice removes [1,4,2] → [3]. Or [4,2,3] → [1]. max(1,3)=3.
    // But Alice could remove [1] → [4,2,3] Bob(n=3,odd). Bob is minimizer.
    //   For odd n, the current player gets max(first,last).
    //   Bob is minimizer with [4,2,3]. If "answer for odd = max(first,last)" applies to
    //   the current player being maximizer, then for Bob (minimizer), it flips.
    //   Hmm I need to be more careful.
    //
    // Let me define f(arr) = optimal result.
    // f(arr of size 1) = arr[0].
    // For the current player (depends on parity of moves made so far):
    //   Actually, Alice always goes first. So with array of size n:
    //   - n elements need n-1 "removal turns" total (at minimum, if 1 removed per turn).
    //   - But turns can remove more.
    //
    // The key observation: the current player can remove a subarray of size 1 to m-1.
    // If they remove m-1 (a prefix or suffix of size m-1), the game ends immediately
    // with either the last or first element.
    //
    // So the current player can always guarantee at least max(first, last) (if maximizer)
    // or at most min(first, last) (if minimizer).
    //
    // But can the maximizer do better? They'd need to leave an array where the next
    // player (minimizer) can't prevent a better outcome. The minimizer will try to get
    // min(first, last) of whatever they face.
    //
    // Let me reconsider: the minimizer can also end the game immediately, guaranteeing
    // min(first, last) of the current array. So the maximizer needs to leave arrays where
    // min(first, last) is still good.
    //
    // For any player, they can end the game by removing m-1 elements. If maximizer,
    // they get max(first,last). If minimizer, they get min(first,last).
    // But they could also not end the game, giving the opponent a smaller array.
    //
    // The maximizer's guaranteed value is max(first, last), since they can always end.
    // Can they do better? Only if by NOT ending, the opponent's response still yields
    // something > max(first, last). But the opponent (minimizer) can always end their
    // turn by taking min(first, last) of whatever they face.
    //
    // If the maximizer removes some subarray (not ending the game), the resulting array
    // is a concatenation of a prefix and suffix. The minimizer then faces this array and
    // can end with min(new_first, new_last).
    // new_first is either first (if we removed from inside-right) and new_last is either
    // last (if we removed from inside-left).
    // If maximizer removes a middle portion, new array has first = original first, last = original last.
    // Then minimizer can end with min(first, last). That's potentially worse for maximizer.
    //
    // So the maximizer should only deviate from ending if there's a guarantee of improvement.
    // Since the minimizer can always get min(first, last) ≤ max(first, last),
    // the maximizer cannot generally improve beyond max(first, last) by continuing.
    //
    // Similarly, the minimizer's guaranteed value is min(first, last), and they cannot
    // generally do better (lower) because the maximizer can always get max(first, last)
    // on the next turn.
    //
    // So:
    // - If it's Alice's turn (maximizer): result = max(first, last)
    // - If it's Bob's turn (minimizer): result = min(first, last)
    // - But we need to figure out who goes first. Alice always goes first.
    // - With n ≥ 2, Alice plays and gets max(nums[0], nums[n-1]).
    //
    // Wait, that gives [1,5,2] → max(1,2) = 2. ✓
    // [3,7] → max(3,7) = 7. ✓
    // n=1 → nums[0]. ✓
    // [1,2,3,4,5] → max(1,5) = 5. ✓
    //
    // But wait, is this always optimal? The maximizer ends immediately getting max(first,last).
    // If they don't end, the minimizer could end getting min(first',last') which could be ≤ max(first,last).
    // So the maximizer never benefits from continuing.
    //
    // Answer = max(nums[0], nums[n-1]) for n ≥ 2, nums[0] for n = 1.

    let n = nums.len();
    if n == 1 {
      nums[0]
    } else {
      nums[0].max(nums[n - 1])
    }
  }
}