Little Romeo likes cosmic amoebas a lot. Recently he found an ancient box, and he believes that there is an amoeba inside it. Unfortunately, the box is protected by a combination lock which contains a row of digits, each between 0 and K, inclusive. The initial combination, from left to right, is given in the String code. Romeo thinks that the lock will open if he replaces each 0 digit with some digit between 1 and K, inclusive, such that the minimal distance between any pair of equal digits is as big as possible. The distance between two numbers in positions A and B, respectively, is |A-B|. Return the maximal possible minimal distance that can be achieved.
| |||||||||||||||||||||||||||||||||||||||||||||||||||||||
