2423 - 나눔의 미학

• Submit
• Status
• Discuss
• Summary

Description

WithCS 유치원에서는 오늘 학생들에게 나눔의 미학을 설명하기 위해 하나의 간단한 게임을 고안해냈다. 우선 학생들을 원형으로 앉혀놓고 원의 중심에 있는 선생님을 바라보게 한다. 이 상태에서 선생님은 학생들에게 짝수개의 사탕들을 나눠줄 것이다. 그러면 학생들마다 가지고있는 사탕의 개수가 들쑥날쑥할 것이다.

 

이제 선생님이 호루라기를 불면 학생들은 동시에 자신이 가지고있는 사탕의 절반을 오른쪽 학생에게 나눠줄 것이다. 만약 왼쪽 친구로부터 받은 사탕까지 포함해서 사탕의 개수가 홀수개가 되면 선생님께 부탁해서 사탕 하나를 더 달라고 말해 사탕의 개수를 짝수로 맞춰놓는다. 

호루라기를 몇번 불고나면 어느순간 모든 학생들이 가지고있는 사탕의 개수가 똑같아질 것이다. 이 모습을 보고 학생들은 "이렇게 규칙적이게 변하다니... 나눔이란 참 멋있구나." 라는 것을 깨닫게 되는, 아주 획기적인 게임인 것이다.

 

이번에 신입으로 들어온 선생님은 호루라기를 최소 몇번을 불어야지 모든 학생들이 가지고있는 사탕의 개수가 똑같아지는지를 모르고있다. 이 선생을 도와서, 학생들이 가지고있는 사탕 정보가 주어졌을 때 호루라기를 몇번 불어야하는지 구해보자.

Input

입력은 여러 테스트케이스로 이루어져있다.

각 테스트케이스마다 첫번째 줄에는 학생의 수 N (1 ≤ N ≤ 100) 이 주어진다.

이어서 N개의 줄에 걸쳐 학생이 몇개의 사탕을 가졌는지를 나타내는 수 Ai가 주어진다. (0 ≤ Ai ≤ 20000) 학생의 순서는 반시계방향 순이다.

 

N으로 0이 들어오면 입력을 종료한다.

Output

각 테스트케이스마다 학생들이 가진 사탕의 개수가 똑같아지게 되는 호루라기 부는 횟수의 최소값과, 이 때 한 학생이 가진 사탕 개수를 출력한다.

Sample Input

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

Sample Output

15 14
17 22
4 8