수족관 점검 기록 정제

문제

한 수족관은 여러 수조의 점검 기록을 하나의 데이터 파일에 저장한다. 각 기록은 0이 아닌 정수 하나이며, 양수 x는 x번 수조의 점검 시작을, 음수 -x는 x번 수조의 점검 종료를 뜻한다. 다른 수조를 점검하는 도중에도 새 점검을 시작할 수 있다. 같은 수조의 점검을 다시 시작한 기록도 별도의 시작 기록으로 취급한다. 수집 장치의 오류 때문에 종료 대상이 맞지 않거나 종료되지 않은 시작 기록이 섞여 있다. 데이터 담당자는 다음 절차를 그대로 적용하여 파일을 정제한다. 기록은 입력 순서대로 한 번씩 확인한다. 시작 기록을 만나면 아직 종료되지 않은 시작 기록들의 맨 뒤에 추가한다. 종료 기록을 만나면 아직 종료되지 않은 시작 기록 중 가장 최근 기록을 확인한다. 그 기록의 수조 번호가 종료 대상과 같으면 두 기록을 한 쌍으로 확정하고, 해당 시작 기록을 미종료 목록에서 제거한다. 미종료 목록이 비어 있거나 가장 최근 시작 기록의 수조 번호가 종료 대상과 다르면 그 종료 기록만 버린다. 이때 더 오래된 시작 기록을 찾아서 연결하지 않으며, 미종료 목록도 바꾸지 않는다. 모든 입력을 확인한 뒤에도 미종료 목록에 남아 있는 시작 기록은 전부 버린다. 이미 확정한 쌍은 이후에 다른 기록을 버리더라도 취소하지 않는다. 정제된 기록은 확정한 쌍에 속하는 기록만 원래 순서대로 남긴 것이다. 이 기록을 처음부터 다시 읽을 때 시작마다 진행 중인 점검 수가 1 증가하고 종료마다 1 감소한다. 정제된 기록에서 진행 중인 점검 수의 최댓값을 최대 동시 점검 수라고 한다. 확정한 쌍의 수, 버린 개별 기록의 수, 최대 동시 점검 수를 구한다. 정제된 기록이 비어 있으면 최대 동시 점검 수는 0이다.

입력

첫째 줄에 기록 수 N이 주어진다. 둘째 줄에 기록 E_1, E_2, …, E_N이 공백으로 구분되어 주어진다. 모든 값은 정수이며, 1 ≤ N ≤ 90,000, 1 ≤ |E_i| ≤ 99이다.

출력

확정한 쌍의 수, 버린 개별 기록의 수, 정제된 기록의 최대 동시 점검 수를 공백으로 구분하여 한 줄에 출력한다.

8
1 2 -1 -2 -1 3 -4 -3

3 2 2

4
1 2 -2 3

1 2 1

5
-2 1 -3 2 -1

0 5 0

출처: Devin.KR 자체 제작