Pyramidal Array#12322
One day, Mar'yan, like every self-respecting boy, decided to go out for a walk with his girlfriend. He ordered flowers, pizza, and children's champagne, but just before leaving the house, he suddenly remembered that he had not solved the problem about the pyramidal array.
The problem is that Mar'yan's parents set a clear condition: until the problem is solved, he is forbidden to go out. Upset, Mar'yan asks you to help him solve this problem as quickly as possible.
An array of elements is called pyramidal if there exists an index (0 \le x < n) such that the following conditions hold:
the element a_x is strictly the largest among all elements of the array and occurs exactly once;
the sequence a_0, a_1, \dots, a_{x-1} is non-decreasing and contains every integer from to a_x - 1 at least once;
the sequence a_{x+1}, a_{x+2}, \dots, a_{n-1} is non-increasing and also contains every integer from to a_x - 1 at least once.
In other words, the array first increases, reaches a unique maximum element, and then decreases, with all values from to a_x - 1 present on both sides of the maximum.
You are given an initial array of length . You must necessarily choose an integer (1 \le c) exactly once and insert it into any position of the array — at the beginning, in the middle, or at the end.
You are also allowed to perform an unlimited number of the following operations:
insert the number at any position in the array.
increase any existing element of the array by .
These two operations cost (inserting the number is free).
Find the minimum cost of operations required to transform the given array into a pyramidal one.
The first line contains an integer (1 \le n \le 2\cdot 10^5) — the number of elements in the array.
The second line contains integers a_0, a_1, \dots, a_{n-1} (1 \le a_i \le 10^9).
Output a single number — the minimum cost of operations required to transform the array into a pyramidal one.
Example 1
Example 2
Example 3
Explanation for the first test case:
Insert the free number c = 2 in the middle of the array, resulting in [1, 1, 2, 1, 1].
The array is already pyramidal, no additional operations are needed.
Cost: .
Explanation for the second test case:
Insert the free number c = 2 at the end: .
To form a pyramid, add another one to the right: [1, 2, 1].
The cost of this operation: , hence the total cost: .
Explanation for the third test case:
Insert the free number c = 3 between and , resulting in [3, 1, 3, 4, 3, 2, 1].
The left part before the peak [3, 1, 3] must become non-decreasing and contain all numbers from to :
Insert at the beginning (cost )
Insert another at the beginning (cost )
Increase the second one to 1 \to 2 (cost )
Increase the fourth one twice to get (cost )
Resulting in a pyramidal array: [1, 2, 3, 3, 3, 4, 3, 2, 1].
Total cost: .
Subtask 1 (10 points): n \le 10, a_i \le 10.
Subtask 2 (30 points): n \le 2 \cdot 10^5, all elements of the array are equal (a_1 = a_2 = \dots = a_n).
Subtask 3 (40 points): n \le 5000.
Subtask 4 (50 points): n \le 2 \cdot 10^5, the number of monotonicity changes (peaks and valleys) is less than . The array changes its direction of increase/decrease at most times.
Subtask 5 (70 points): n \le 2 \cdot 10^5, the array is sorted in non-decreasing order.
Subtask 6 (150 points): No additional constraints.