Min Num Letters

Given a word consisting only of lowercase English letters, find the minimum number of letters to delete so that the remaining letters, in their original relative order, form a lexicographically non-decreasing string. The remaining letters do not have to be contiguous, and equal letters may all be kept.

输入格式

One line containing a non-empty string S. 1≤|S|≤100000, and S contains only a-z.

输出格式

Output the minimum number of letters to delete.

样例 1

输入：

banana

输出：

3

样例说明

The kept part must be a non-decreasing subsequence of the original string. The minimum number of deletions equals |S| minus the length of the longest non-decreasing subsequence.