학원 출결 로그의 연쇄 정제

문제

한 학원은 여러 교실에서 모은 출결 로그를 하나의 파일에 저장한다. 로그의 각 항목에는 학생을 나타내는 양의 정수 코드 하나가 들어 있다. 코드는 학생의 이름과 관계없는 내부 식별자이며, 같은 학생의 코드는 언제나 같다. 데이터 담당자는 이 파일에 섞인 중복 전송 흔적을 정해진 규칙에 따라 정제해야 한다. 이 학원에서 사용하는 전송 장치는 통신을 재시도할 때 같은 항목을 두 번 연속 남기는 경우가 있다. 정제 작업에서는 현재 남아 있는 로그에서 서로 이웃한 두 코드가 같으면 그 두 항목을 함께 삭제한다. 항목 하나만 지우거나 서로 떨어진 항목을 한꺼번에 삭제할 수는 없다. 삭제된 자리의 왼쪽과 오른쪽에 항목이 남아 있으면 두 항목은 새롭게 이웃하게 된다. 정제 순서에 대한 해석이 달라지지 않도록 다음 절차를 사용한다. 현재 로그에 삭제할 수 있는 쌍이 여러 개 있으면 가장 왼쪽에 있는 쌍을 삭제한다. 삭제한 뒤에는 남은 로그의 처음부터 다시 살펴본다. 이 과정을 서로 이웃한 같은 코드가 하나도 없을 때까지 반복한다. 어떤 코드가 세 번 연속 있으면 그중 가장 왼쪽 두 항목이 먼저 삭제되어 하나가 남는다. 네 번 연속 있으면 네 항목이 모두 삭제된다. 삭제 때문에 이전에는 떨어져 있던 같은 코드가 만나면 그 두 항목도 다음 정제 대상이 된다. 예를 들어 코드의 순서가 4, 7, 7, 4이면 가운데 두 항목을 삭제한 뒤 남은 두 항목도 삭제한다. 반면 같은 코드가 파일 안에 여러 번 등장한다는 이유만으로 삭제하지는 않는다. 정제 과정에서 살아남은 항목의 상대적인 순서는 바뀌지 않는다. 모든 정제가 끝났을 때 남은 항목 수와 코드의 순서를 구해야 한다. 아무 항목도 남지 않는 경우도 정상적인 정제 결과로 취급한다. 원본 로그는 한 개 이상 주어지며, 입력 파일 전체에 대해 정제 작업을 한 번 수행한다.

입력

첫째 줄에 원본 로그의 항목 수 N이 주어진다. N은 1 이상 200,000 이하의 정수다.
둘째 줄에 로그의 코드 N개가 원래 순서대로 공백으로 구분되어 주어진다. 각 코드는 1 이상 100,000 이하의 정수다.

출력

첫째 줄에 정제 후 남은 항목 수 K를 출력한다. K가 양수이면 둘째 줄에 남은 코드 K개를 순서대로 공백으로 구분하여 출력한다. K가 0이면 둘째 줄을 출력하지 않는다.

8
3 5 5 3 2 2 8 9

2
8 9

6
6 6 6 6 6 6

0

5
1 2 1 2 1

5
1 2 1 2 1

출처: Devin.KR 자체 제작