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.

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.

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