영어 원문입니다. 원문의 수식·표를 글자로 옮겨 모양이 다를 수 있습니다. 정확한 내용은 원문 페이지에서 확인하세요. 원문 페이지 열기 (새 창)
Problem
The mail carrier Harry Kuvert is careless. When he today stands at the beginning of the street along which he is to deliver the post, he has not sorted the letters.
When he reads the letter on top of the pile, he has two choices:
- Either he puts the letter in his bag to possibly deliver it tomorrow
- Or he finds the correct address and delivers the letter
Since Harry lives at the end of the street, he refuses to turn around and go back. The letters that end up on top of the pile and whose address he has already passed therefore go directly into the bag. Despite everything, Harry has a little mail carrier's heart that beats a little extra when he manages, using his method, to deliver as many letters as possible.
Write a program that receives a string of uppercase letters A-Z, where no letter can appear more than once. The number of letters can vary but cannot exceed 26. This string describes Harry's pile of letters, with the top letter first. Since the street is “numbered” from A to Z, the program should find the longest subsequence of the string where the letters are in ascending order. This subsequence gives the maximum possible number of delivered letters — something Harry can achieve if he always makes the right choice.
Input
The input is a string S (1 ≤ |S| ≤ 26) consisting of uppercase letters A-Z. Each letter appears at most once in the string.
Output
Output the longest string that is a subsequence of the input string such that all letters are in alphabetical order. If there are multiple equally good solutions, it suffices to output any of them.
예제
예제 1
KBWZSROCFUJDEILANTMYGVXHPQ
BCDEILNTVX