Get Minimum Operations (Sort with Proper-Substring Sort)

Each operation chooses any non-empty proper substring (not the whole string) and sorts its characters in ascending order. Find the minimum number of operations needed to sort the whole string in ascending order.

输入格式

A single line containing a lowercase string of length 3..100000.

输出格式

Output a single integer answer.

样例 1

输入：

zyxpqa

输出：

3

样例 2

输入：

abc

输出：

0

样例 3

输入：

bac

输出：

1

样例说明

Example 1: the first character z is the unique maximum and the last character a is the unique minimum, so 3 operations are needed: sort the first 5, the last 5, and the first 5 characters in turn. Example 2: already sorted, 0 operations. Example 3: the last c is already the maximum, so sorting the first two characters ba is enough, 1 operation.