Safe Cracking

A safe lock consists of N rotating dials. Each dial has the numbers from 0 to M-1 written around it. If a dial showing M-1 is rotated one more step, it becomes 0.

The safe opens when every dial shows the same number. Dials can only be rotated in the direction that increases their number, and rotating one dial by one step takes 1 second.

A consecutive group of dials that currently show the same number can be rotated together. Regardless of the length of the group, increasing all of them by one step takes 1 second. For example, from the state (1, 1, 1, 2), the three leftmost dials can be rotated together for 1 second so that they all become 2.

Given the initial state of the lock, find the minimum time required to open the safe.

The first line contains N, the number of dials, and M, the number of possible values. (1 ≤ N ≤ 500, 2 ≤ M ≤ 10,000)

The second line contains N integers: the initial numbers shown on the dials.

Print the minimum time required to open the safe.

For the initial state (9, 0, 1, 0, 3), one possible optimal sequence is:

• Initial state: (9, 0, 1, 0, 3)
• After 1 second: (9, 0, 1, 1, 3)
• After 2 seconds: (0, 0, 1, 1, 3)
• After 3 seconds: (1, 1, 1, 1, 3)
• After 4 seconds: (2, 2, 2, 2, 3)
• After 5 seconds: (3, 3, 3, 3, 3)

So the safe can be opened in 5 seconds.