[Solution] Sorting Pancakes solution codeforces

Sorting Pancakes solution codeforces – Nastya baked 𝑚m pancakes and spread them on 𝑛n dishes. The dishes are in a row and numbered from left to right. She put 𝑎𝑖ai pancakes on the dish with the index 𝑖i.

[Solution] Sorting Pancakes solution codeforces

Seeing the dishes, Vlad decided to bring order to the stacks and move some pancakes. In one move, he can shift one pancake from any dish to the closest one, that is, select the dish 𝑖i (𝑎𝑖>0ai>0) and do one of the following:

  • if 𝑖>1i>1, put the pancake on a dish with the previous index, after this move 𝑎𝑖=𝑎𝑖1ai=ai−1 and 𝑎𝑖1=𝑎𝑖1+1ai−1=ai−1+1;
  • if 𝑖<𝑛i<n, put the pancake on a dish with the following index, after this move 𝑎𝑖=𝑎𝑖1ai=ai−1 and 𝑎𝑖+1=𝑎𝑖+1+1ai+1=ai+1+1.

Vlad wants to make the array 𝑎anon-increasing, after moving as few pancakes as possible. Help him find the minimum number of moves needed for this.

The array 𝑎=[𝑎1,𝑎2,,𝑎𝑛]a=[a1,a2,…,an] is called non-increasing if 𝑎𝑖𝑎𝑖+1ai≥ai+1 for all 𝑖i from 11 to 𝑛1n−1.

Input

The first line of the input contains two numbers 𝑛n and 𝑚m (1𝑛,𝑚2501≤n,m≤250) — the number of dishes and the number of pancakes, respectively.

The second line contains 𝑛n numbers 𝑎𝑖ai (0𝑎𝑖𝑚0≤ai≤m), the sum of all 𝑎𝑖ai is equal to 𝑚m.

[Solution] Sorting Pancakes solution codeforces

Print a single number: the minimum number of moves required to make the array 𝑎a non-increasing.

Examples
input

Copy
6 19
5 3 2 3 3 3
output

Copy
2
input

Copy
3 6
3 2 1
output

Copy
0

[Solution] Sorting Pancakes solution codeforces

input

Copy
3 6
2 1 3
output

Copy
1
input

Copy
6 19
3 4 3 3 5 1
output

Copy
3

[Solution] Sorting Pancakes solution codeforces

input

Copy
10 1
0 0 0 0 0 0 0 0 0 1
output

Copy
9
Note

In the first example, you first need to move the pancake from the dish 11, after which 𝑎=[4,4,2,3,3,3]a=[4,4,2,3,3,3]. After that, you need to move the pancake from the dish 22 to the dish 33 and the array will become non-growing 𝑎=[4,3,3,3,3,3]a=[4,3,3,3,3,3].

For Solution

Click here

Leave a Comment