Palindromization
Description
Palindromes are sequences that read the same both left-to-right and right-to-left. Such sequences play a significant role in string algorithms. Programmer Vlad believes that working with palindromes is easier than with any other strings or arrays, so whenever Vlad sees an array, he strives to turn it into a palindrome.
This time, Vlad received an array $a$ of $n$ integers. In one operation, Vlad can choose any segment of this array and add the same number $x$ from $1$ to $k$ inclusive to all elements on this segment.
Despite being accustomed to working with palindromes, this time Vlad encountered problems with turning $a$ into a palindrome with the minimum number of actions. Help him quickly cope with this task.
The first line of input contains two integers $n$ and $k$ — the size of the original array and the limit on the added values ($1 \le n \le 10^6$; $1 \le k \le 3$).
The second line of input contains $n$ space-separated integers $a_i$ — the elements of the array ($1 \le a_i \le 10^9$).
Output a single number — the minimum number of operations required to turn the array $a$ into a palindrome.
Scoring
Points for each subtask are awarded only if all tests of that subtask and the required subtasks are successfully passed.
| Subtask | Points | Constraints | Required subtasks | |
| 0 | – | examples | ||
| 1 | 10 | $n, a_i \le 10$ | 0 | |
| 2 | 11 | $a_i \le 2$, $k=1$ | ||
| 3 | 12 | $a_i \le a_{i+1}$ for all $i | lt; n$ | |
| 4 | 20 | $k = 1$ | 2 | |
| 5 | 22 | $k \le 2$ | 4 | |
| 6 | 25 | $k \le 3$, $n \le 1000$ | 0, 1 |
Notice that there is no group with $k = 3$ and no additional constraints!
Input
The first line of input contains two integers $n$ and $k$ — the size of the original array and the limit on the added values ($1 \le n \le 10^6$; $1 \le k \le 3$).
The second line of input contains $n$ space-separated integers $a_i$ — the elements of the array ($1 \le a_i \le 10^9$).
Output
Output a single number — the minimum number of operations required to turn the array $a$ into a palindrome.
5 1
1 2 3 4 5
6 2
3 6 4 1 2 5
8 3
1 4 3 1 2 1 1 2
4
4
3
Note
In the first example, you need to add $1$ to the segment $[1, 3]$, add $1$ to the segment [$1, 2$], and then add $1$ twice to the first element. Thus, after four operations, the array equals $[5, 4, 4, 4, 5]$.
In the second example, you need to add $2$ to the segment $[1, 1]$, add $2$ to the segment $[4, 5]$ and add $1$ to the segment $[4, 5]$, after which add $1$ to the segment $[5, 5]$. Thus, after four operations, the array equals $[5, 6, 4, 4, 6, 5]$.
In the third example, you need to add $1$ to the segment $[1, 4]$, add $3$ to the segment $[6, 7]$ and add $1$ to the segment $[7, 7]$. Thus, after three operations, the array equals $[2, 5, 4, 2, 2, 4, 5, 2]$.