You may reorder arr and decrease any value to a smaller positive integer as many times as needed. The final array must begin with 1, and neighboring values must differ by at most 1. Return the greatest element value that any valid final array can contain.
Example 1:
Input: arr = [3,1,2]
Output: 3Explanation: Rearrange the entries into [1,2,3]. It starts with 1 and adjacent differences are 1, so the maximum is 3.
Example 2:
Input: arr = [1,1,100]
Output: 2Explanation: Keep the two 1s and decrease 100 to 2, obtaining [1,1,2]. The last entry cannot exceed 2 because it follows a 1.
Example 3:
Input: arr = [10,10,10]
Output: 3Explanation: Decrease and arrange the entries as [1,2,3]. Three positions starting at 1 with increases of at most 1 cannot reach beyond 3.
Constraints:
1 <= arr.length <= 1000001 <= arr[i] <= 1000000000