Maximum Element After Decreasing and Rearranging
You are given an array of positive integers arr. Perform some operations (possibly none) on arr so that it satisfies these conditions:
- The value of the first element in
arrmust be1. - The absolute difference between any 2 adjacent elements must be less than or equal to
1. In other words,abs(arr[i] - arr[i - 1]) <= 1for eachiwhere1 <= i < arr.length(0-indexed).abs(x)is the absolute value ofx.
There are 2 types of operations that you can perform any number of times:
- Decrease the value of any element of
arrto a smaller positive integer. - Rearrange the elements of
arrto be in any order.
Return the maximum possible value of an element in arr after performing the operations to satisfy the conditions.
Example 1
Input
arr = [2,2,1,2,1]Output
2We can satisfy the conditions by rearranging
arr so it becomes [1,2,2,2,1], whose largest element is 2.Example 2
Input
arr = [100,1,1000]Output
3After rearranging to
[1,100,1000] and decreasing the second and third elements, arr can become [1,2,3], whose largest element is 3.Constraints
- 1 <= arr.length <= 10^5
- 1 <= arr[i] <= 10^9