WC '18 Finals J1 - Conditional Contracts

View as PDF

Submit solution

Points: 5 (partial)
Time limit: 1.0s
Memory limit: 16M

Author:
Problem type
Woburn Challenge 2018-19 Finals Round - Junior Division

The cows and monkeys of Scarberia, their long-standing conflicts well behind them at last, have banded together to produce a historical drama documenting their past battles. With the Head Monkey as writer and producer, and the director's chair occupied by the cows' leader, Bo Vine, this will be a collaborative masterpiece to remember!

As part of his preparations, Bo Vine is considering what width of film to use, an important artistic decision. He doesn't want to limit himself to a single width, so he's decided that two copies of the movie will be shot, on two different film widths! Each film width (measured in mm) must be an integer between 11 and 1\,000\,000\,0001\,000\,000\,000, inclusive, and the two widths must be distinct.

There are NN (1 \le N \le 100)(1 \le N \le 100) acclaimed actors interested in the film, and the Head Monkey and Bo Vine would like to cast as many of them as possible. However, they only work under very specific conditions- the ii-th actor insists that they must be captured on film with a width of exactly W_iW_i mm (1 \le W_i \le 1\,000\,000\,000)(1 \le W_i \le 1\,000\,000\,000). Each actor can be employed if their requirement is satisfied for at least one of the two copies of the movie.

If Bo Vine chooses a pair of distinct film widths optimally, what's the maximum number of different actors who can be employed?

Subtasks

In test cases worth 50\%50\% of the points, W_i \le 100W_i \le 100 for each ii.

Input Specification

The first line of input consists of a single integer, NN.
NN lines follow, the ii-th of which consists of a single integer, W_iW_i, for i = 1 \dots Ni = 1 \dots N.

Output Specification

Output a single integer, the maximum number of actors who can be employed.

Sample Input

4
50
70
51
70

Sample Output

3

Sample Explanation

One possibility is using 5050mm film for the first copy of the movie and 7070mm film for the second copy. This allows the first, second, and fourth actors to be employed. It's impossible for all 44 actors to be employed at once.


Comments

There are no comments at the moment.