세탁 바구니의 양말 묶음

문제

세탁소에서는 세탁과 건조를 마친 양말을 손님에게 돌려주기 전에 두 개씩 묶는다. 작업대에는 왼쪽부터 오른쪽으로 N개의 바구니가 놓여 있으며, 바구니에는 순서대로 1번부터 N번까지 번호가 붙어 있다. 각 바구니에는 한 손님의 양말만 들어 있고, 같은 바구니에 들어 있는 양말은 크기와 색이 모두 같아서 어느 두 개를 골라도 하나의 묶음으로 만들 수 있다. 서로 다른 바구니의 양말은 손님이 다르므로 절대로 함께 묶을 수 없다. 따라서 앞 바구니에 양말이 하나 남았더라도 다음 바구니의 양말과 합쳐서 묶음을 만들지는 않는다. 이미 묶은 양말을 다른 바구니로 옮기는 일도 없다. 양말이 없는 바구니 역시 작업대에 놓여 있을 수 있으며, 이런 바구니에서는 묶음도 남는 양말도 생기지 않는다. 직원은 바구니를 번호순으로 살펴본다. 현재 바구니에 묶지 않은 양말이 두 개 이상 있으면 두 개를 꺼내 묶는 작업을 반복한다. 묶지 않은 양말이 한 개 이하가 되면 그 바구니의 작업을 끝내고 다음 바구니로 이동한다. 양말을 버리거나 새로 가져오는 일은 없으므로 작업이 끝난 각 바구니에는 묶지 않은 양말이 없거나 한 개만 남는다. 작업 기록에는 각 바구니에 처음 들어 있던 양말의 개수가 배열의 순서대로 적혀 있다. 직원은 모든 바구니의 작업을 마친 뒤, 완성한 묶음의 총개수와 묶지 못하고 남은 양말의 총개수를 기록하려 한다. 바구니별 결과를 따로 출력할 필요는 없으며, 모든 바구니에서 나온 두 종류의 개수를 각각 합하면 된다. 주어진 기록을 이용하여 이 두 값을 구하는 프로그램을 작성한다.

입력

첫째 줄에 바구니 수를 나타내는 정수 N이 주어진다. 1 ≤ N ≤ 1,000이다.
둘째 줄에 각 바구니에 들어 있는 양말 수 A_1, A_2, …, A_N이 공백으로 주어진다. 모든 A_i는 정수이며 0 ≤ A_i ≤ 1,000이다.

출력

완성한 묶음의 총개수와 묶지 못한 양말의 총개수를 이 순서대로 한 줄에 공백으로 구분하여 출력한다. 해당하는 개수가 없으면 그 값으로 0을 출력한다.

5
3 0 6 1 4

6 2

3
1 1 1

0 3

1
0

0 0

출처: Devin.KR 자체 제작