你有字符串 s,仅包含小写英文字母。找到它的字典顺序最大子序列。
我们将非空字符串 s[p1p2... pk] = sp1sp2... spk(1 ≤ p1 < p2 < ... < pk ≤ |s|) 称为字符串 s = s1s2... s|s| 的子序列。
字符串 x = x1x2... x|x|按字典顺序大于字符串 y = y1y2... y|y|,如果 |x| > |y|且 x1 = y1, x2 = y2, ... , x|y| = y|y|,或存在这样的数字 r (r < |x|, r < |y|),即 x1 = y1,x2 = y2,...,xr = yr 和 xr + 1 > yr + 1。行中的字符像其 ASCII 代码一样进行比较。
输入
单行包含一个非空字符串 s,仅由小写英文字母组成。字符串的长度不超过105。
输出
打印字符串 s 的字典顺序最大子序列。
示例
输入 #1
ababba
输出 #1
bbba
输入 #2
abbcbccacbbcbaaba
输出 #2
cccccbba
注意
让我们看一下样本,看看所寻找的子序列是什么样的(它们用大写粗体字母标记)。
第一个样本:aBaBBA
第二个样本:abbCbCCaCbbCBaaBA