관측판의 상쇄 표식

문제

한 천문대는 밤하늘에서 들어오는 신호를 네 종류로 분류한다. 각 종류는 대문자 A, B, C, D 중 하나로 표시한다. 관측 장치는 신호가 도착할 때마다 그 종류를 기록하며, 하룻밤 동안 기록한 신호를 도착 순서대로 이어 붙인 문자열을 만든다. 이 문자열에 등장하는 모든 문자는 하나의 신호를 나타낸다. 연구원은 반복 신호를 정리하기 위해 별도의 관측판을 사용한다. 관측판은 처음에 비어 있으며, 아직 상쇄되지 않은 표식을 왼쪽부터 순서대로 보관한다. 연구원은 입력 문자열의 첫 문자부터 마지막 문자까지 각 신호를 정확히 한 번씩 처리한다. 처리 도중에 다음 신호를 건너뛰거나 이미 처리한 신호를 다시 읽는 일은 없다. 새 신호를 처리할 때 관측판이 비어 있으면 그 신호의 표식을 관측판에 적는다. 관측판이 비어 있지 않으면 새 신호와 관측판의 맨 오른쪽 표식을 비교한다. 두 종류가 다르면 새 표식을 맨 오른쪽에 덧붙인다. 두 종류가 같으면 맨 오른쪽 표식을 지우고, 새 신호의 표식도 적지 않는다. 이때 두 신호가 한 쌍으로 상쇄되었다고 하며 상쇄 횟수를 1만큼 늘린다. 한 신호를 처리하면서 상쇄는 최대 한 번만 일어난다. 상쇄로 인해 이전 표식이 드러나더라도 그 순간에는 추가 작업을 하지 않고 다음 입력 신호를 처리한다. 나중에 도착한 신호가 새로 드러난 맨 오른쪽 표식과 같다면 그때 다시 상쇄될 수 있다. 예를 들어 ABBA를 순서대로 처리하면 가운데의 B 두 개가 먼저 상쇄되고, 마지막 A가 남아 있던 A와 상쇄되어 관측판이 비게 된다. 모든 신호를 처리했을 때 발생한 상쇄 횟수와 관측판에 남은 표식의 문자열을 구한다. 남은 표식은 관측판의 왼쪽부터 오른쪽까지 읽는다. 관측판이 비었다면 남은 문자열 대신 정해진 단어 EMPTY를 기록한다.

입력

첫째 줄에 신호 수를 나타내는 정수 N이 주어진다. 1 ≤ N ≤ 100,000이다.
둘째 줄에 길이가 정확히 N인 문자열이 주어진다. 문자열의 각 문자는 대문자 A, B, C, D 중 하나이며 공백은 없다.

출력

첫째 줄에 전체 상쇄 횟수를 정수로 출력한다. 상쇄가 한 번도 일어나지 않았으면 0을 출력한다. 둘째 줄에 관측판에 남은 문자열을 출력한다. 관측판이 비어 있으면 대문자로 EMPTY를 출력한다.

8
ABBACDDC

4
EMPTY

9
AABCCBDDA

4
A

5
ABCDA

0
ABCDA

출처: Devin.KR 자체 제작