COCI '13 Contest 1 #5 Organizator

Points: 15 (partial)

Time limit: 0.6s

Memory limit: 256M

Problem type

Unexpected problems with law enforcement have convinced Mirko to take up a less lucrative but less morally ambiguous career: he has become the chief organizer of a team computer science contest.

There are $N$ $N$ CS clubs that wish to participate in the contest. The presidents of the clubs are quite stubborn and will participate in the contest only if the contest team size makes it possible for all club members to participate.

The contest consists of two rounds: qualifications and finals. All teams that are competing must have an equal number of members and all members of one team must belong to the same club. Any number of teams from each club can participate in the qualification round, and the best team from each club earns a spot in the finals.

Mirko is aware that, with a new and unproven contest, he needs publicity. For that reason, he wants to set the team size such that the number of individual participants in the finals is as large as possible. Remember, each club that participates has a right to one team in the finals. Furthermore, at least two clubs must participate in the contest, otherwise the contest would be too boring to attract sponsors.

Determine the maximum possible number of participants in the finals so that Mirko can double check his team size choice.

Input

The first line of input contains the positive integer $N$ $N$ $(2 \le N \le 200\,000)$ $(2 \leq N \leq 200 000)$ , the number of clubs.

The second line of input contains $N$ $N$ space-separated integers from the interval $[1, 2\,000\,000]$ $[1, 2 000 000]$ , the number of members of each club.

Output

The first and only line of output must contain the maximum possible number of finalists.

Scoring

In test data worth at least $30\%$ $30 %$ of total points, $N$ $N$ will be less than $1000$ $1000$ .

Sample Input 1

Copy

3
1 2 4

Sample Output 1

Copy

Explanation

Mirko decides on $2$ $2$ members per team, so clubs $2$ $2$ and $3$ $3$ participate.

Sample Input 2

Copy

2
1 5

Sample Output 2

Copy

Sample Input 3

Copy

5
4 6 3 8 9

Sample Output 3

Copy

Comments

7

1419903188 commented on Aug. 28, 2018, 3:24 a.m.

Problem type

The problem type should be math instead of dynamic programming in my opinion.🤔

-7

A_H_Ghaznavi commented on June 15, 2019, 6:58 p.m.

Why?

This problem has a clear dp solution.

This comment is hidden due to too much negative feedback. Show it anyway.

6

ross_cleary commented on May 31, 2020, 1:43 a.m.

Making a frequency array and naming it "dp" does not constitute a dp solution. This problem should be tagged as intermediate math.

7

Xyene commented on June 12, 2016, 4:38 p.m. ← edit 3 →

An issue in the official test data was discovered by jeffreyxiao, and has been fixed. All submissions have been rejudged.

Congratulations to those who now have AC!