WC '18 Finals J1 - Conditional Contracts

View as PDF

Submit solution

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

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 1 and 1\,000\,000\,000, inclusive, and the two widths must be distinct.

There are N (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 i-th actor insists that they must be captured on film with a width of exactly W_i mm (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?


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

Input Specification

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

Output Specification

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

Sample Input


Sample Output


Sample Explanation

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


There are no comments at the moment.