시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율
2 초 128 MB 118 45 41 43.158%

문제

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

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

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

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

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

입력

첫째 줄에 N이 주어진다. N은 1보다 크거나 같고, 8보다 작거나 같다. 둘째 줄에, N개의 데이터가 주어진다. 합은 항상 100이다.

출력

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

예제 입력

4
10 40 10 40

예제 출력

2

힌트

출처