메뉴 건너뛰기

문제


시간메모리제출 회통과 회비율
1초128MB
0
0
0.0%
나의 횟수나의 판정시도 명성공 명비율
00
0.0%
문제

두 명이 하는 카드 게임이 있다.

  • \(1\)부터 \(2n\)까지 수가 적힌 카드 \(2n\)장을 쓴다. \(n\)은 \(1\) 이상 \(100\) 이하이다.
  • 두 사람에게 카드를 \(n\)장씩 나눈다.
  • 번갈아 카드 한 장을 장에 낸다.
    • 장에 카드가 없으면 아무 카드나 낼 수 있다.
    • 장에 카드가 있으면, 마지막에 낸 카드보다 큰 수가 적힌 카드만 낼 수 있다.
    • 낼 수 있으면 반드시 내야 한다.
    • 낼 카드가 없으면 패스하고 상대 차례가 되며, 이때 장의 카드는 없어진다.
  • 게임은 장이 빈 상태로 시작한다.
  • 어느 한쪽의 손이 없어지면 게임이 끝난다.
  • 게임이 끝났을 때 상대가 가진 카드 수가 점수이다.

타로와 하나가 이 게임으로 대결한다. 타로부터 시작한다. 둘 다 낼 수 있는 카드 중 가장 작은 수만 낸다.

타로에게 나눠 준 카드가 주어지면, 타로와 하나의 점수를 출력하는 프로그램을 작성하라.

입력

입력은 다음 형식으로 주어진다.

\(n\)

\(A_1\)

\(\vdots\)

\(A_n\)

  • 첫째 줄에 \(n\)이 주어진다.
  • 다음 \(n\)줄에 타로가 받은 카드의 수가 한 줄에 하나씩 주어진다.
  • 타로가 받지 않은 \(n\)장은 하나가 가진다.
  • 입력되는 값은 모두 정수이다.
출력

다음 형식으로 출력한다.

첫째 줄에 타로의 점수, 둘째 줄에 하나의 점수를 출력한다.

예시 1
입력
5 1 7 9 6 10
출력
3 0
예시 2
입력
10 8 7 14 18 4 11 3 17 5 19
출력
2 0
위로