A. Lexicographically Maximum Subsequencetime limit per test2 secondsmemory limit per test256 megabytesinputstandard inputoutputstandard outputYou've got string s, consisting of only lowercase English letters. Find its lexicographically maximum subsequence.We'll call a non-empty string s[p1p2... pk] = sp1sp2... spk(1 ≤ p1 < p2 < ... < pk ≤ |s|) a subsequence of string s = s1s2... s|s|.String x = x1x2... x|x| is lexicographically larger than string y = y1y2... y|y|, if either |x| > |y| and x1 = y1, x2 = y2, ... , x|y| = y|y|, or exists such number r (r < |x|, r < |y|), that x1 = y1, x2 = y2, ... , xr = yr and xr + 1 > yr + 1. Characters in lines are compared like their ASCII codes.InputThe single line contains a non-empty string s, consisting only of lowercase English letters. The string's length doesn't exceed 105.OutputPrint the lexicographically maximum subsequence of string s.ExamplesInputababbaOutputbbbaInputabbcbccacbbcbaabaOutputcccccbbaNoteLet's look at samples and see what the sought subsequences look like (they are marked with uppercase bold letters).The first sample: aBaBBAThe second sample: abbCbCCaCbbCBaaBA
Inputababba
Outputbbba
['greedy', 'strings', '*1100']