410392: GYM104015 J Replacing Letters
Description
Monocarp has got a string $$$s$$$ consisting of lowercase Latin letters.
Monocarp likes non-descending strings. A string is called non-descending if for each pair of positions $$$[i, j]$$$ where $$$i < j$$$ the following condition is met: the $$$i$$$-th letter of the string appears not later in the alphabet than the $$$j$$$-th letter of the string. For example, the strings "aaa", "bcdef", "aappszz" are non-descending, but the strings "ba", "abcba", "zzzzzx" are not
Monocarp wants his string $$$s$$$ to become non-descending. To achieve his goal, he can replace any letters in the string with any other letters. Calculate the minimum number of letters in $$$s$$$ that should be replaced to make $$$s$$$ non-descending, and print the resulting string $$$s$$$.
InputThe first line contains one integer $$$n$$$ ($$$2 \le n \le 200\,000$$$) — the length of $$$s$$$.
The second line contains the string $$$s$$$ consisting of $$$n$$$ lowercase Latin letters.
OutputIn the first line, print one integer $$$x$$$ — the minimum number of letters that should be replaced in $$$s$$$ so it becomes non-descending.
In the second line, print the resulting string — a non-descending string that can be obtained from $$$s$$$ by replacing $$$x$$$ letters. If there are multiple answers, print any of them.
ExamplesInput5 efahiOutput
1 efghiInput
10 aaaabceehhOutput
0 aaaabceehhInput
8 fgdadvfdOutput
5 dddddddd