시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율
1 초 128 MB 10 7 7 77.778%

문제

학생들이 선생님을 중심으로 서로 마주보며 둥글게 앉아있다. 학생들은 각각 짝수개의 사탕을 가지고 있다. 선생님이 호루라기를 부는 순간 학생들은 자신의 오른쪽 학생에게 사탕의 반을 준다. 이 때 학생들 중 홀수개의 사탕을 가지게 되는 학생들은 선생님으로부터 하나의 사탕을 더 받게 된다. 모든 학생들의 사탕의 개수가 같아지면 게임은 끝나게 된다.

선생님이 호루라기를 부는 횟수와 게임이 끝났을 때 한 학생이 받는 사탕의 개수를 구해보자.

입력

입력은 여러개의 게임으로 이루어져 있다. 각 게임의 첫번째 줄에는 학생들의 수 N이 주어지며, 다음 N개에 줄에 시계방향 순으로 각 학생들이 가지고 있는 사탕의 개수가 한 줄에 하나씩 주어진다. 학생의 수 N이 0일 때 프로그램을 종료한다. N은 10만보다 작거나 같은 자연수이다.

출력

각 게임이 끝났을 때 라운드 수와 학생들이 가지고 있게 되는 사탕의 수를 공백으로 구분하여 출력한다.

예제 입력

6
36
2
2
2
2
2
11
22
20
18
16
14
12
10
8
6
4
2
4
2
4
6
8
0

예제 출력

15 14
17 22
4 8

힌트

게임은 무한히 진행되지 않는다. 그 이유는 4가지가 있는데, 각자 생각해 보자.