Lexicographically Maximum Subsequence

2000ms

262144K

Description:

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₁p₂... p_k] = s_p₁s_p₂... s_{p_k}(1 ≤ p₁ < p₂ < ... < p_k ≤ |s|) a subsequence of string s = s₁s₂... s_|s|.

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

Input:

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

Output:

Print the lexicographically maximum subsequence of string s.

Sample Input:

ababba

Sample Output:

bbba

Sample Input:

abbcbccacbbcbaaba

Sample Output:

cccccbba

Note:

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

Informação

Provedor Codeforces

Código CF196A