You are given a $0$ indexed integer array maxHeights of length $n$.

Your task is to construct an array heights of length $n$ such that:

• $1 \leq$ heights[i] $\leq$ maxHeights[i] for all $0 \leq i < n$.

• heights forms a mountain array, meaning there exists an index $i$ such that:

  • heights[j] $\leq$ heights[j + 1] for all $0 \leq j < i$

  • heights[k] $\geq$ heights[k + 1] for all $i \leq k < n - 1$

Return the maximum possible sum of elements in heights for any valid configuration.

Constraints:

• $1 \leq n ==$ maxHeights.length $\leq 10^5$

• $1 \leq$ maxHeights[i] $\leq 10^9$

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.