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

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.