A8646. Lexicographically Maximum Subsequence

You've got string $s$ , consisting of only lowercase English letters. Find its lexicographically maximum subsequence.

We'll call a non-empty string $s[p_{1}p_{2}...\ p_{k}]=s_{p1}s_{p2}...\ s_{pk}(1<=p_{1}<p_{2}<...<p_{k}<=|s|)$ a subsequence of string $s=s_{1}s_{2}...\ s_{|s|}$ .

String $x=x_{1}x_{2}...\ x_{|x|}$ is lexicographically larger than string $y=y_{1}y_{2}...\ y_{|y|}$ , if either $|x|>|y|$ and $x_{1}=y_{1},x_{2}=y_{2},...\ ,x_{|y|}=y_{|y|}$ , or exists such number $r$ $(r<|x|,r<|y|)$ , that $x_{1}=y_{1},x_{2}=y_{2},...\ ,x_{r}=y_{r}$ and $x_{r+1}>y_{r+1}$ . Characters in lines are compared like their ASCII codes.

The single line contains a non-empty string $s$ , consisting only of lowercase English letters. The string's length doesn't exceed $10^{5}$ .

Print the lexicographically maximum subsequence of string $s$ .

Let's look at samples and see what the sought subsequences look like (they are marked with uppercase bold letters).

The first sample: aBaBBA

The second sample: abbCbCCaCbbCBaaBA