창고 라벨의 연쇄 회수

문제

물류 창고에서는 출고 대기 상자에 붙인 라벨을 하나의 문자열로 기록한다. 문자열의 각 문자는 상자 한 개의 라벨 종류를 나타내며, 문자가 놓인 순서는 상자가 운반대에 들어오는 순서와 같다. 라벨 종류는 영어 대문자 한 글자로 구분한다. 같은 종류의 라벨이 붙은 상자 두 개가 운반대의 맨 뒤에서 이웃하게 되면 두 상자를 함께 회수한다. 운반대는 처음에 비어 있다. 작업자는 기록의 첫 문자부터 마지막 문자까지 차례대로 읽는다. 문자를 하나 읽을 때마다 그 문자에 해당하는 상자를 운반대의 맨 뒤에 놓는다. 이때 새 상자와 바로 앞 상자의 라벨이 같으면 두 상자를 즉시 회수한다. 운반대에 상자가 하나뿐이거나 두 라벨이 다르면 회수하지 않는다. 회수가 끝난 뒤에야 다음 문자를 읽는다. 이미 회수한 상자는 다시 들어오지 않으며, 남은 상자의 상대적인 순서는 바뀌지 않는다. 예를 들어 기록이 ABBA라면 A와 B가 차례대로 놓인 뒤, 세 번째 B가 앞의 B와 함께 회수된다. 마지막 A는 운반대에 남아 있던 A와 함께 회수된다. 따라서 모든 기록을 처리한 뒤에는 운반대가 비게 된다. 서로 떨어져 있는 같은 라벨을 임의로 골라 회수할 수는 없다. 창고 관리자는 모든 상자의 입고 기록을 처리한 뒤 실제로 남는 라벨 목록을 확인하려 한다. 주어진 규칙대로 작업을 수행하여 남은 상자의 수와 라벨 문자열을 구해야 한다. 남은 문자열은 운반대의 앞에서 뒤로 읽은 순서로 출력한다. 남은 상자가 없으면 빈 문자열 대신 하이픈 한 글자를 출력한다.

입력

첫째 줄에 기록의 길이인 정수 N이 주어진다. 1≤N≤200,000이다.
둘째 줄에 길이가 정확히 N인 문자열 S가 주어진다. S는 영어 대문자 A부터 Z까지만 포함한다.

출력

첫째 줄에 남은 상자의 수를 출력한다. 둘째 줄에 남은 라벨 문자열을 출력한다. 남은 상자가 없으면 -를 출력한다.

8
ABBACDDC

0
-

7
ABCCBDA

3
ADA

출처: Devin.KR 자체 제작