택배 선반의 빈칸 정리

문제

택배 작업장에는 왼쪽부터 오른쪽으로 일렬로 놓인 N개의 선반 칸이 있다. 각 칸에는 택배가 하나 놓여 있거나 아무것도 놓여 있지 않다. 작업자는 선반을 한 번 스캔해 각 칸의 값을 배열로 저장했다. 값이 0이면 빈칸이고, 양의 정수이면 그 칸에 놓인 택배의 분류 번호이다. 분류 번호는 택배를 구별하는 고유 번호가 아니므로 같은 번호가 여러 칸에 나타날 수 있다. 다음 작업을 시작하기 전에 모든 택배를 선반의 왼쪽으로 모으려 한다. 이때 택배끼리의 상대적인 순서는 반드시 유지해야 한다. 정리 전에 어떤 택배가 다른 택배보다 왼쪽에 있었다면, 정리 후에도 그 택배가 더 왼쪽에 있어야 한다. 분류 번호가 작다는 이유로 앞으로 보내거나, 같은 분류 번호의 택배를 하나로 합쳐서는 안 된다. 정리가 끝난 선반에서는 첫 번째 칸부터 택배가 빈틈없이 이어지고, 남은 빈칸은 모두 오른쪽 끝에 모여 있어야 한다. 택배를 추가하거나 없애지 않으므로 선반의 전체 칸 수는 정리 전과 동일하게 N개이다. 모든 칸이 비어 있었다면 정리 후에도 모든 칸이 비어 있다. 반대로 빈칸이 하나도 없었다면 선반에 기록된 값의 순서가 그대로 유지된다. 작업자는 실제 선반을 옮기기 전에 스캔 결과만으로 정리 후의 모습을 확인하려 한다. 입력된 배열에서 택배가 놓인 칸의 수를 구하고, 위 규칙에 따라 정리한 선반의 배열을 출력한다. 여기서 구하는 개수는 서로 다른 분류 번호의 수가 아니라 놓여 있는 택배 전체의 수이다. 옮겨야 하는 거리나 실제로 움직인 택배의 수는 계산하지 않는다. 규칙을 모두 만족하는 정리 후 배열은 하나로 결정된다.

입력

첫째 줄에 선반의 칸 수를 나타내는 정수 N이 주어진다. 1≤N≤100,000이다.
둘째 줄에 왼쪽 칸부터 순서대로 정수 a1, a2, …, aN이 공백으로 주어진다. 모든 i에 대해 0≤ai≤999이다. 0은 빈칸을 나타내고, 1부터 999까지의 값은 택배의 분류 번호를 나타낸다.

출력

첫째 줄에 선반에 놓인 택배의 수를 정수로 출력한다. 둘째 줄에 정리 후 선반의 N개 값을 왼쪽부터 공백으로 구분해 출력한다. 택배가 하나도 없어도 둘째 줄에 N개의 0을 출력한다.

8
0 12 0 7 7 0 3 0

4
12 7 7 3 0 0 0 0

3
0 0 0

0
0 0 0

1
999

1
999

출처: Devin.KR 자체 제작