시간 제한메모리 제한제출정답맞힌 사람정답 비율
2 초 128 MB123854144746.178%

문제

민식이는 학교에서 다른 반 친구들이 개를 몇 마리 키우는지 궁금했다. 그래서, 세준이는 다른 반 친구들이 키우는 개의 수를 조사했다. 세준이네 학교에 개를 키우는 사람의 수는 총 100명이었다. 어떤 반에 개를 키우는 사람이 15명이면, 이 것은 15%와 같다.

민식이는 자기가 조사한 개의 수를 가지고 원형 차트를 만들었다. 10, 40, 10, 40 일때의 차트 모양은 다음과 같다.

또, 10, 40, 50 일때의 차트 모양은 다음과 같다.

민식이가 조사한 데이터를 이용해서 차트를 만들 수 있는 방법은 여러 가지가 존재한다. 민식이는 그 중에, 원의 중심을 지나는 선의 개수를 최대로 하고 싶어한다. (원의 중심을 지나는 선이란, 원을 이등분하는 선)

민식이 학교의 반의 개수와, 각 반에서 개를 키우는 사람의 수가 주어졌을 때, 원의 중심을 지나는 선의 개수의 최댓값을 출력하는 프로그램을 작성하시오.

입력

첫째 줄에 N이 주어진다. N은 1보다 크거나 같고, 8보다 작거나 같다. 둘째 줄에, 민식이가 조사한 개의 수가 주어진다. 개의 수는 100 이하의 자연수이고, 조사한 개의 수의 합은 항상 100이다.

출력

첫째 줄에 정답을 출력한다.

예제 입력 1

4
10 40 10 40

예제 출력 1

2

예제 입력 2

3
10 50 40

예제 출력 2

1

예제 입력 3

2
50 50

예제 출력 3

1

예제 입력 4

6
1 48 1 1 48 1

예제 출력 4

3

예제 입력 5

3
2 2 96

예제 출력 5

0

출처