Given a string strValue, find the minimum number of operations required to sort the string.

Operation Allowed

In one operation, you may:

• Choose any proper substring of strValue
• Sort that substring

Important Definitions

• A substring is contiguous
• A proper substring is any substring except the entire string
• A string S is a substring of T if S can be obtained by deleting characters from the beginning and/or end of T

Goal

Make the entire string sorted in non-decreasing order using the minimum number of operations.

Example

Input

strValue = "zyxpqa"

Explanation of Optimal Operations

• Sort substring [0..4] → "zyxpq" → "pqxyz"
• Sort substring [1..5]
• Sort substring [0..1]

After 3 operations, the string becomes sorted.

Output

3

Function Description

Complete the function:

int getMinimumOperations(string strValue)

Constraints

• 3 ≤ |strValue| ≤ 10⁵
• strValue contains only lowercase English letters (a–z)

Sample Inputs & Outputs

Additional Examples

Example 1

Input

strValue = "acb"

One optimal operation

• Sort substring [1..2] → "cb" → "bc", resulting string becomes "abc"

Output

1

Example 2

Input

strValue = "abca"

One optimal operation

• Sort substring [1..3] → "bca" → "abc", resulting string becomes "aabc"

Output

1