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~.
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 a single integer, the maximum number of actors who can be employed.
4 50 70 51 70
One possibility is using ~50~mm film for the first copy of the movie and ~70~mm 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.