Problem Brief

Maximum Final Value (Also for AS Intern)

INTERNNEW GRADOA

See Amazon online assessment and hiring insights

Amazon’s development team has shared a coding task for you to solve.

You are given a list of integers and need to perform operations to ensure the following conditions are met:

The first number of the list must be 1.

or every other position, the difference between consecutive numbers must not exceed 1. Specifically, for 1 ≤ i < n, the condition numbers[i] - numbers[i - 1] ≤ 1 must hold.

To achieve this, you are allowed to perform the following operations:

Rearrange the elements in any order.

Decrease any number to any value, but no lower than 1.

Your objective is to calculate the highest possible value of the last number in the list after applying the allowed operations and meeting all conditions.

1Example 1

Input

numbers = [3, 1, 3, 4]

Output

Explanation

The steps to achieve the maximum possible final value are as follows: Reduce the first element by 1, changing the array to [2, 1, 3, 4]. Rearrange the array to form [1, 2, 3, 4]. After these operations, the last element's value becomes 4, which is the highest possible. Therefore, the result is 4.

Constraints

Limits and guarantees your solution can rely on.

1 <= n <= 10^5

1 <= arr[i] <= 10^9

Draft autosaves locally

public int maximumFinal(int[] numbers) {
  // write your code here
}

Input

numbers

[3, 1, 3, 4]

Output