## GUPTA MECHANICAL

IN THIS WEBSITE I CAN TELL ALL ABOUT TECH. TIPS AND TRICKS APP REVIEWS AND UNBOXINGS ALSO TECH. NEWS .............

## Unlock the Padlock Round B 2022 - Kick Start 2022

### Problem

Imagine you have a padlock, which is a combination lock consisting of $N$ dials, set initially to a random combination. The dials of the padlock are of size $D$, which means that they can have values between $0$ and $\mathbf{D}-1$, inclusive, and can be rotated upwards or downwards. They are also ordered from left to right, with the leftmost and rightmost dials at positions $1$ and $N$, respectively. The padlock can be unlocked by setting the values of all its dials to $0$.

You can perform zero or more operations of this kind:

• Pick any range $\left[l,r\right]$ such that $1\le l\le r\le \mathbf{N}$ and rotate all the dials in $\left[l,r\right]$ together, upwards or downwards. Rotating up increases the value of each dial in the range $\left[l,r\right]$ by $1$, and rotating down decreases its value by $1$. Note that a dial with value $\mathbf{D}-1$ becomes $0$ when increased (rotated up) and a dial with value $0$ becomes $\mathbf{D}-1$ when decreased (rotated down).

The series of operations must satisfy the following condition:

• The range $\left[{l}_{i-1},{r}_{i-1}\right]$ chosen in the $\left(i-1\right)$-th operation needs to be completely contained within the range $\left[{l}_{i},{r}_{i}\right]$ chosen in the $i$-th operation; that is, ${l}_{i}\le {l}_{i-1}\le {r}_{i-1}\le {r}_{i}$. The initial range ($\left[{l}_{1},{r}_{1}\right]$) can be chosen arbitrarily.

Example of a valid sequence of operations to unlock a padlock with initial combination $\left[1,1,2,2,3,3\right]$:

1. Rotate range $\left[5,6\right]$ downwards.
2. Rotate range $\left[3,6\right]$ downwards.
3. Rotate range $\left[1,6\right]$ downwards.

The following are some operations that cannot be performed:

1. Rotating range $\left[1,4\right]$ after $\left[6,9\right]$, because $\left[6,9\right]$ is not completely contained in $\left[1,4\right]$ (does not satisfy ${r}_{i-1}\le {r}_{i}$ where ${r}_{i-1}=9$ and ${r}_{i}=4$).
2. Rotating range $\left[3,6\right]$ after $\left[2,7\right]$.

The goal for you is to output the minimum number of valid operations needed to make all dials in the padlock set to $0$.

### Input

The first line of the input contains the number of test cases, $T$$T$ test cases follow.

Each test case consists of two lines.

The first line of each test case contains two integers $N$ and $D$, representing the number of dials in the padlock and the size of the dials, respectively.

The second line of each test case contains $N$ integers ${\mathbf{V}}_{\mathbf{1}},{\mathbf{V}}_{\mathbf{2}},\dots ,{\mathbf{V}}_{\mathbf{N}}$, where the $i$-th integer represents the value of the $i$-th dial in the initial combination of the padlock.

### Output

For each test case, output one line containing Case #x$x$: y$y$, where $x$ is the test case number (starting from $1$) and $y$ is the minimum number of operations needed to unlock the padlock as described in the statement.

### Limits

Time limit: 30 seconds.
Memory limit: 1 GB.
$1\le \mathbf{T}\le 100$.
$0\le {\mathbf{V}}_{\mathbf{i}}\le \mathbf{D}-1$, for all $i$.

#### Test Set 1

$1\le \mathbf{N}\le 40$.
$\mathbf{D}=2$.

#### Test Set 2

$1\le \mathbf{N}\le 40$.
$2\le \mathbf{D}\le 10$.

#### Test Set 3

$1\le \mathbf{N}\le 400$.
$2\le \mathbf{D}\le {10}^{9}$.

### Sample

Note: there are additional samples that are not run on submissions down below.
Sample Input
2
6 2
1 1 0 1 0 1
6 2
0 1 0 0 1 1

Sample Output
Case #1: 3
Case #2: 2


In Sample Case #1, the minimum number of operations needed to unlock the padlock is $3$. We can unlock it using the following operations:

1. Rotate range $\left[4,4\right]$ downwards.
2. Rotate range $\left[3,5\right]$ downwards.
3. Rotate range $\left[1,6\right]$ downwards.

In Sample Case #2, the minimum number of operations needed to unlock the padlock is $2$. We can unlock it using the following operations:

1. Rotate range $\left[3,4\right]$ upwards.
2. Rotate range $\left[2,6\right]$ downwards.

Solution Click Below:-

### Additional Sample - Test Set 2

The following additional sample fits the limits of Test Set 2. It will not be run against your submitted solutions.
Sample Input
2
6 10
1 1 2 2 3 3
6 10
1 1 9 9 1 1

Sample Output
Case #1: 3
Case #2: 3


In Sample Case #1, the minimum number of operations needed to unlock the padlock is $3$. We can unlock it using the following operations:

1. Rotate range $\left[5,6\right]$ downwards.
2. Rotate range $\left[3,6\right]$ downwards.
3. Rotate range $\left[1,6\right]$ downwards.

In Sample Case #2, the minimum number of operations needed to unlock the padlock is $3$. We can unlock it using the following operations:

1. Rotate range $\left[3,4\right]$ upwards.
2. Rotate range $\left[3,4\right]$ upwards.
3. Rotate range $\left[1,6\right]$ downwards.