Longest Increasing Subsequence in a Melody

You are given a melody represented as a string where each character denotes a musical note. The notes are compared using their lexicographical order (i.e. the ASCII order). Your task is to determine the length of the longest strictly increasing subsequence of notes in the given melody.

A subsequence is a sequence that can be derived from the string by deleting some or no elements without changing the order of the remaining elements. For example, in the melody abcaebd, one of the longest increasing subsequences is a, b, e, d (where each note is larger than its predecessor when compared lexicographically) and its length is 4.

The problem requires you to read from the standard input and output the result to the standard output.

Note: If the melody is empty, the output should be 0.

inputFormat

The input consists of a single line containing a non-empty string melody representing the sequence of musical notes.

Input Format:

melody

outputFormat

Output a single integer which is the length of the longest strictly increasing subsequence of the melody.

Output Format:

result

## sample

abcaebd

4