Build the Highest Valid Value by Decreasing and Rearranging

### Problem You may rearrange `arr` freely and decrease an entry to a smaller positive integer. Make the first entry one and every adjacent absolute difference at most one. Return the greatest element value that a valid resulting array can contain. ```cpp class Solution { public: int maximumElementAfterDecrementingAndRearranging(vector<int>& arr); }; ``` ### Examples **Example 1:** ```text arr = [3,1,5,2] Output: 4 Explanation: Sort and decrease to [1,2,3,4]. A length-four array starting at 1 cannot exceed 4. ``` **Example 2:** ```text arr = [1,1,4] Output: 2 Explanation: Two entries must remain 1, so the remaining entry can be lowered to 2. ``` ### Constraints - `1 <= arr.length <= 10^5`. - `1 <= arr[i] <= 10^9`. ### Clarifying Questions Decreases keep values positive; increases are forbidden. The output is a greatest value, not an operation count. ```hint Inspect the structure Which entries may decrease, what stays positive, and what must the first final entry be? ``` ### Reasoning checkpoints - Use only permitted decreases and rearrangements, retaining positivity and the fixed first value. - Prove that the reported maximum is achievable and no larger value satisfies the adjacent-difference rule. ### Optional extensions How could counting values capped at the array length give a linear-time alternative?