Rearrange Books on the Shelf

You are given a string s where each character represents a book labeled by a lowercase letter. The books are arranged in a specific order on a shelf. Your task is to determine the minimum number of operations required to rearrange the books so that they are in non-decreasing order (i.e., sorted in increasing order).

An operation is defined implicitly, and it can be interpreted as the removal or repositioning of a book. In fact, the problem is equivalent to finding the minimum number of moves required to retain the longest non-decreasing subsequence, and then the result is obtained as:

\(n - LNS\)

where \(n\) is the total number of books and \(LNS\) is the length of the longest non-decreasing subsequence (with respect to the alphabetical order).

For example, if s = "cba", the answer is 2 since by keeping only one correctly ordered book, you effectively need to reposition the others.

inputFormat

Input is read from standard input (stdin) as a single line containing the string representing the books on the shelf. The string consists only of lowercase English letters.

outputFormat

Output the minimum number of operations required to rearrange the books in non-decreasing order. The result should be printed to standard output (stdout) as an integer.## sample

cba

2