410392: GYM104015 J Replacing Letters

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$$$.

The 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.

In 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.

5
efahi

1
efghi

10
aaaabceehh

0
aaaabceehh

8
fgdadvfd

5
dddddddd