시간 제한메모리 제한제출정답맞힌 사람정답 비율
1 초 256 MB1841089261.333%

문제

경영고등학교 근처에는 프로야구팀 kt wiz의 홈구장 ‘수원 케이티 위즈 파크’가 있다. 경영고의 야구팬들은 대부분 어렸을 때부터 프로야구를 좋아했기 때문에 새로 kt wiz의 팬이 된 사람들은 드물지만, 경영고의 야구팬들은 그저 야구 경기를 직관하기 위해서 야간자율학습 시간에 선생님들 몰래 야구를 보러 간다.

이번에도 N명의 학생들이 선생님들 몰래 야구경기를 보려고 한다. N명의 학생들 중 일부는 1루 응원석(홈 응원석)에서 야구를 보며, 일부는 3루 응원석(원정 응원석)에서 야구를 보며, 나머지는 외야석에서 야구를 본다.

하지만, 이번에는 경영고의 문학 선생님께서 학생 감시 차원에서 야구 경기를 직관하기 때문에, 선생님은 야구 경기를 보는 곳에 학생들이 있으면 단체로 기합을 준 다음에 학교로 보내려고 한다. 선생님과 다른 곳에 있는 학생들도 선생님이 왔다는 사실은 알기 때문에 한 회가 끝나면 몰래 자리를 이동한다. (있던 곳에 그대로 머무를 수도 있다) 문학 선생님 역시 경영고의 학생들이 야구를 보고 있다는 사실을 알기 때문에 다른 곳으로 이동하여 학생들을 잡을 수 있다. 다만, 문학 선생님이 직전 회에 있었던 곳에 그대로 머무를 수도 있다. 문학 선생님은 학생들이 자신의 위치를 알지 못하도록 몰래몰래 움직인다.

경영고의 N명의 학생들은 문학 선생님이 어디에 있든지 상관없이 9회 동안 어디에 가서 야구를 볼지 미리 정해놓았다. 한편, 문학 선생님은 매 회마다 무작위의 장소에서 야구를 본다. 운이 좋으면 N명의 학생 모두 야구를 끝까지 볼 수도 있겠지만, 운이 나쁘면 N명의 학생 모두 선생님에게 혼날 지도 모른다. 경영고의 학생들 중에서 야구를 끝까지 볼 수 있는 학생 수의 범위를 구하는 프로그램을 작성하여라. 단, 야구 경기가 무승부라서 연장전에 돌입하는 경우는 없다고 가정해도 좋다.

입력

첫 번째 줄에는 학생의 수 N이 주어진다. (2 ≤ N ≤ 300,000)

두 번째 줄부터 N개의 줄에는 각 학생들이 9회 동안 있을 곳의 번호가 주어진다. 1은 1루 응원석, 2는 외야석, 3은 3루 응원석을 의미한다.

출력

첫 번째 줄에 야구를 끝까지 볼 수 있는 학생의 수의 최솟값과 최댓값을 출력한다.

예제 입력 1

7
1 2 3 1 2 3 1 2 3
2 3 1 2 3 1 2 3 1
3 1 2 3 1 2 3 1 2
1 1 1 2 2 2 3 3 3
2 2 2 3 3 3 1 1 1
3 3 3 1 1 1 2 2 2
1 3 1 3 1 3 1 3 1

예제 출력 1

0 3

힌트

만약 문학 선생님이 항상 1루 응원석에 있다면, 1, 4, 7번째 학생은 1회 때 들키고, 3번째 학생은 2회 때, 2번째 학생은 3회 때, 6번째 학생은 4회 때, 5번째 학생은 7회 때 들키므로 모든 학생들이 야구를 끝까지 볼 수 없다.

하지만, 문학 선생님이 3루->1루->3루->1루->외야->외야->3루->외야->외야로 이동한다면 2, 5, 7번 학생이 야구를 끝까지 볼 수 있다.

문학 선생님이 어떻게 이동하더라도 4명 이상의 학생이 야구를 끝까지 볼 수 있는 방법은 없다.

출처

Contest > BOJ User Contest > FunctionCup > FunctionCup 2016 B번