우편배달부

우편배달부 Harry Kuvert는 부주의하다. 오늘 우편물을 배달할 거리가 시작되는 곳에 섰을 때, 그는 편지를 정리해 두지 않았다.

편지 더미의 맨 위에 있는 편지를 읽을 때, 그에게는 두 가지 선택지가 있다:

• 편지를 가방에 넣어 두었다가 내일 배달할 수도 있다

• 또는 올바른 주소를 찾아 편지를 배달한다

Harry는 거리 끝에 살며, 그는 돌아서서 되돌아가기를 거부한다. 따라서 편지 더미의 맨 위에 올라왔지만 그 주소를 이미 지나친 편지는 곧바로 가방에 들어간다. 그럼에도 해리에게는 작은 우편배달부의 마음이 있어, 자신의 방법으로 가능한 한 많은 편지를 배달하는 데 성공하면 조금 더 세차게 뛴다.

대문자 A-Z로 이루어지고 어떤 문자도 한 번보다 많이 등장할 수 없는 문자열을 입력받는 프로그램을 작성하라. 문자의 개수는 달라질 수 있지만 26을 초과할 수 없다. 이 문자열은 맨 위의 편지가 먼저 오도록 해리의 편지 더미를 나타낸다. 거리가 A부터 Z까지 ``번호가 매겨져'' 있으므로, 프로그램은 문자가 오름차순으로 놓인 문자열의 가장 긴 부분 수열을 찾아야 한다. 이 부분 수열은 배달할 수 있는 편지 수의 최댓값을 나타내며, 해리가 항상 올바른 선택을 한다면 이를 달성할 수 있다.

입력은 대문자 A-Z로 이루어진 문자열 $S$ ($1 \leq |S| \leq 26$)이다. 각 문자는 문자열에 최대 한 번 등장한다.

입력 문자열의 부분 수열이면서 모든 문자가 알파벳 순서로 놓인 가장 긴 문자열을 출력한다. 동일하게 좋은 답이 여러 개라면, 그중 아무거나 출력해도 충분하다.