데이지와 사랑

$M > 1$인 M-호감 상태 목록은 다음과 같이 정의되는 수열이다. 첫 번째 항은 상태 “사랑함”이고, 나머지 $M-1$개의 항은 (서로 다른) 임의의 호감 상태들이다.

소녀는 소년이 준 데이지 꽃의 꽃잎을 하나씩 뜯으면서 다음 규칙으로 소년의 마음을 읽는다.

1. 첫 번째 꽃잎을 뜯기 전에는 상태 “사랑함”에 있다.
2. 꽃잎을 하나 뜯을 때마다 호감 상태는 목록의 다음 상태로 바뀐다.
3. 목록의 마지막 상태 다음 상태는 다시 “사랑함”이다(목록은 순환한다).
4. 꽃에 더 이상 꽃잎이 없으면 그 데이지에 대한 처리를 끝내고, 그때의 상태를 결과로 반환한다.

예를 들어 $3$개짜리 목록 “사랑함”-“좋아함”-“무관심”을 생각하자. 이 목록에서는 꽃잎이 $5$개인 데이지의 결과는 “무관심”이고, $7$개인 데이지의 결과는 “좋아함”이다.

소녀는 소년이 준 데이지들이 모두 상태 “사랑함”을 가리킬 때에만 소년이 자신을 사랑한다고 믿는다. 소년은 소녀를 설득하고 싶어서, 소녀에게 데이지 $N$송이를 주고 가능한 한 긴 호감 상태 목록을 직접 정의하려고 한다.

주어진 데이지들에 대해, 소녀가 소년이 자신을 사랑한다고 결론짓게 되는 가장 큰 $M$ 값을 구하여라.

첫째 줄에 데이지의 개수 $N$ ($1 \le N \le 1000$)이 주어진다. 둘째 줄에 $N$개의 정수 $L_i$ ($1 \le L_i \le 100$)가 공백으로 구분되어 주어지며, $L_i$는 $i$번째 데이지의 꽃잎 개수이다.

가능한 가장 큰 $M$ 값을 정수 하나로 출력한다. 만약 데이지들의 꽃잎 개수에 $1$보다 큰 공약수가 없으면 $1$을 출력한다.