Minimum Increasing Substrings

You are given a string S consisting of digit characters. Your task is to partition this string into the fewest possible substrings such that each substring forms a strictly increasing sequence. A strictly increasing sequence means that for any substring consisting of characters \(s_1s_2\ldots s_k\), the following condition holds: \(s_1 < s_2 < \cdots < s_k\).

For example, if \(S = \) 1234, then the entire string is strictly increasing so the answer is 1. However, if \(S = \) 1325, the best you can do is partition it into 13 and 25 since 2 is not greater than 3, so the answer is 2.

If the input string is empty, consider the answer to be 0.

inputFormat

The input consists of a single line containing the string S composed only of digits (0-9). This string may possibly be empty.

outputFormat

Output a single integer which is the minimum number of substrings required such that each substring is a strictly increasing sequence.

1234

1