Minimum Removals for Non-Decreasing Sequence

You are given a string (s) consisting of lowercase English letters. Your task is to remove the minimum number of characters such that the remaining characters form a non-decreasing sequence in lexicographical order. In other words, after removal, for every valid index (i), the condition (s[i] \leq s[i+1]) must hold. This problem can be solved by determining the length of the longest subsequence that is already non-decreasing (or equivalently, finding the longest increasing subsequence under the condition of non-decrease) and subtracting its length from the total length of the string.

inputFormat

The input consists of a single line containing a string (s) composed of lowercase English letters.

outputFormat

Output a single integer which represents the minimum number of characters that must be removed from (s) to make the remaining sequence non-decreasing.## sample

abcdbca

3