ENG  RUSTimus Online Judge
Online Judge
Problems
Authors
Online contests
About Online Judge
Frequently asked questions
Site news
Webboard
Links
Problem set
Submit solution
Judge status
Guide
Register
Update your info
Authors ranklist
Current contest
Scheduled contests
Past contests
Rules

1431. Diplomas

Time limit: 1.0 second
Memory limit: 64 MB
It might be interesting for you to learn that there are students who take part in various contests instead of studying. Sometimes such students are even awarded diplomas for winning these contests. Another amusing fact is that some deans collect and hang on the walls color copies of student diplomas. And when there are too many diplomas, extra walls are put up in a dean's office. But before a new wall is put up, its size should be determined, and for that a scheme of arranging diplomas on the wall is needed. That is why a designer is usually hired, to make everything beautiful.
A hired designer reckons that all diplomas of the same kind (for example, for winning semifinals) must be in the same row, and each row may contain diplomas of at most two different kinds. Moreover, if a row contains diplomas of two kinds, then they must alternate, and the last diploma in the row must be of the same kind as the first one for the sake of symmetry.
In order to determine how many walls should be put up, the dean has to know the minimal number of rows needed to arrange all the diplomas (the rows can be unboundedly long). Of course, having such clever students, it's not a big problem. That is to say, it is a problem, but a problem for the students.

Input

The first line of the input contains the number of different kinds of diplomas N (1 ≤ N ≤ 18). The second line contains the numbers of diplomas of each kind separated with a space: N integers in the range from 1 to 30.

Output

You should output the minimal number of rows needed to arrange the diplomas in accordance with the designer's requirements.

Sample

inputoutput
6
8 15 13 8 14 8
5
Problem Author: Stanislav Vasilyev
Problem Source: The 7th USU Open Personal Contest - February 25, 2006