Longest Non-Decreasing Subsequence

Given a string \(S\) consisting of lowercase letters, your task is to determine the length of the longest subsequence of \(S\) whose characters are in non-decreasing order. A subsequence is a sequence that can be derived from the original string by deleting some or no elements without changing the order of the remaining characters.

Formally, for a subsequence \(a_1, a_2, \ldots, a_k\) extracted from \(S\), it must hold that:

[ a_1 \leq a_2 \leq \cdots \leq a_k ]

For example, in the string "abcpqr", the entire string is a valid non-decreasing subsequence, so the answer is 6. However, for the string "zyx", any single character is a valid subsequence, and the answer is 1.

You are required to read the input from standard input (stdin) and output the answer to standard output (stdout).

inputFormat

The input consists of a single line containing the string \(S\). The string will contain only lowercase letters. Note that \(S\) may be empty.

outputFormat

Output a single integer representing the length of the longest non-decreasing subsequence of \(S\).

abcpqr

6