A single string is a string consisting of ~1~ character, with a length equal to the position of that character in the alphabet. For example:
a, bb, dddd are valid single strings.
ab, aa, bbbb are not single strings.
A grafted string is a string composed of multiple single strings concatenated together, and the preceding single string must have a character that is less than the character of the following single string. For example:
a, abb, adddd are valid grafted strings.
bba, aabb, bbbb are not grafted strings.
Given a string ~s~ consisting of lowercase letters, find the longest subsequence (not necessarily contiguous) in ~s~ that is a grafted string. Output the length of that string.
Input
A single line containing the string ~s~ ~(|s| \leq 10^5)~.
Output
Output the length of the longest subsequence that satisfies the problem statement.
Scoring
Subtask | Points | Limits |
---|---|---|
1 | ~20\%~ | ~|s| \leq 20~ |
2 | ~30\%~ | ~|s| \leq 5000~ |
3 | ~50\%~ | No additional limits. |
Sample Input 1
adddebbaacccd
Sample Output 1
6
Sample Input 2
abbcdccddd
Sample Output 2
7
Notes
In example ~1~: The longest grafted string in the example test is abbccc.
In example ~2~: The longest grafted string in the example test is abbdddd.
Comments