Make Array Bitonic

Given an array arr of n integers, in a single operation, one can reduce any element of the array by 1. Find the minimum number of operations required to make the array a bitonic* array.

• A bitonic array can have any number of zeros in prefix and suffix. The non-zero part should increase from 1 to some integer k and then decrease to 1. Example of a bitonic array: [0,1,2,3,2,1,0,0].

Constraints

N/A

Example 1

Input:

arr = [3,3,3,3,3]

Output:

6

Explanation: Answer: 6 (Final Array: [1,2,3,2,1])

Example 2

Input:

arr = [1,1,3,1,1]

Output:

3

Explanation: Answer: 3 (Final Array: [0,1,2,1,0])

Example 3

Input:

arr = [1,2,1,3,2]

Output:

5

Explanation: Answer: 5 (Final Array: [1,2,1,0,0] or [0,0,1,2,1])