페이지가 로드되지 않나요? 여기를 눌러보면 고쳐질 수도 있어요.
Placeholder

#2735

대회 1초 64MB

문제

플루오르 대륙에서 대륙단위 대회를 주최하였다.

이 대회는 예선과 결선으로 이루어지며, 팀 단위 시합이다.

한편, 한 팀에는 무조건 L명의 용사들로만 구성되어야 한다. L은 주최 측에서 결정하는 수이다. 만약 L=1이면 이 대회는 개인전이다.

플루오르 대륙에는 N개의 마을이 있는데, 각 마을에는 Pk명의 용사들이 있다.

각 마을에서는 용사들을 L명씩 묶어서 팀을 만든 후, 그 팀들 중에서 가장 강한 팀을 뽑아서 그 팀만을 결선에 내보낸다.

만약 예선에 참여하지 못하는 용사가 있을 경우(즉, Pk가 L의 배수가 아닐 경우)에는 공정성을 위해 그 마을에서 결선 진출 팀을 내보내지 않는다.

한편, 결선에서는 예선에서 승리한 팀들을 대상으로 다시 시합을 해서 가장 강한 팀을 뽑는다. 이 때, 결선에 진출한 팀은 두 팀 이상이여야 한다.

민규는 이 대회에서 L을 결정하는 역할을 맡았다. 대회가 성대하게 진행되려면 결선에 진출하는 용사의 수가 최대한 많아야 한다.

플루오르 대륙에는 마을이 너무 많기 때문에 손으로 L을 구하기는 힘들다. 민규를 위해 L을 구해주는 프로그램을 만들자.


입력

첫 번째 줄에는 마을의 수 N이 주어진다. (2 ≤ N ≤ 200,000)

두 번째 줄에는 각 마을의 인구 Pk가 주어진다. (1 ≤ Pk ≤ 2,000,000)


출력

결선에 진출하는 용사의 수의 최댓값을 출력한다.


예제1

입력
3

124
출력
4

예제2

입력
2

15
출력
2

예제3

입력
5

46389
출력
9

출처

COCI 2013/2014 Contest 1 Task 5 ORGANIZATOR

역링크