회의실 배지 감지

문제

한 회의실의 출입구에는 참가자의 배지를 읽는 감지 장치가 있다. 각 참가자의 배지에는 영문 소문자로 이루어진 코드가 적혀 있으며, 서로 다른 참가자는 서로 다른 코드를 사용한다. 코드의 길이가 다르거나 어느 한 글자라도 다르면 서로 다른 코드이다. 코드가 비슷하게 생겼더라도 일부 글자를 생략하거나 바꾸어서 비교하지 않는다. 기록을 시작하는 시점에는 회의실 안에 아무도 없다. 참가자는 회의실에 들어갈 때와 회의실에서 나갈 때 모두 배지를 정확히 한 번 읽힌다. 장치는 배지의 코드만 기록하며, 들어가는 행동인지 나가는 행동인지는 따로 기록하지 않는다. 다만 각 참가자의 현재 위치와 반대되는 쪽으로 이동할 때만 배지를 읽힌다는 규칙이 보장된다. 따라서 회의실 밖에 있는 참가자의 코드가 기록되면 그 참가자가 들어온 것이고, 안에 있는 참가자의 코드가 기록되면 그 참가자가 나간 것이다. 어떤 참가자가 처음 등장하면 그 참가자는 회의실 밖에 있던 것으로 본다. 한 참가자가 회의 중 여러 번 나갔다가 다시 들어오는 것도 가능하다. 모든 출입은 주어진 기록 순서대로 한 명씩 일어나며, 하나의 기록을 처리하는 도중에 다른 출입이 일어나지 않는다. 기록되지 않은 출입이나 배지를 읽히기만 하고 이동하지 않는 행동은 없다. 관리자는 모든 기록을 처리한 직후 회의실에 남아 있는 사람 수와, 기록을 처리하는 동안 회의실에 동시에 있었던 사람 수의 최댓값을 알고 싶다. 최댓값을 구할 때는 처음의 빈 상태와 각 기록을 처리한 직후의 상태를 모두 고려한다. 마지막에 회의실이 비어 있어도 이전에 사람이 많았던 상태는 최댓값 계산에 포함한다. 두 사람 수를 구하는 프로그램을 작성한다. 사람이 없는 상태의 사람 수는 0이며, 참가자의 코드나 최댓값을 처음 달성한 시점은 출력하지 않는다.

입력

첫째 줄에 기록 수 N이 주어진다. N은 1 이상 100,000 이하의 정수이다.
다음 N개 줄에는 기록된 배지 코드가 시간 순서대로 하나씩 주어진다. 각 코드는 영문 소문자로만 이루어져 있고 길이는 1 이상 12 이하이다.

출력

모든 기록을 처리한 직후 남아 있는 사람 수와 동시에 있었던 사람 수의 최댓값을 공백으로 구분하여 한 줄에 출력한다.

5
a
b
a
c
b

1 2

4
aa
aa
b
b

0 1

6
sun
moon
star
moon
moon
sun

2 3

출처: Devin.KR 자체 제작