Box of Chocolates#258

Box of Chocolates

1 second
64 megabytes
Easy
prb258

Vitya received a huge box of chocolates for his birthday. Each candy is shaped like a round chocolate coin wrapped in gold or silver foil. Vitya is not a greedy boy, so he decided to share the candies with his younger sister Mariyka. Vitya called Mariyka and invited her to pick chocolates herself. To make it more interesting, he allowed Mariyka to choose any chocolates, provided the following rules are satisfied:

  1. All chocolates are arranged strictly horizontally.

  2. Each chocolate is either on the surface of the table, or on another chocolate. Thus, several chocolates may form a pile.

  3. All selected chocolates must be in a single pile.

  4. In a pile, you may place either one chocolate of smaller radius on another, or four chocolates, but such that their edges do not extend beyond the edges of the chocolate below them.

Of course, Mariyka loves chocolate, so she wants to take as many as possible. How many chocolates can she take? The box contains so many chocolates that Vitya is not afraid that if Mariyka stacks a heap, there will not be enough. For example, if the box contains chocolates of radii , , , and , then in the bottom layer you can put the first chocolate of radius , on it four chocolates of radius , and on each of those, four chocolates of radius . In total, 1 + 4 + 4 \cdot 4 = 21 chocolates.

Input

The first line of the input file contains the number (0 \le N \le 1000) — the number of types of chocolates in the box. The next line contains integers — the radii of the chocolates, each not exceeding .

Output

Output the maximum number of chocolates Mariyka can take.

Examples

Example 1

Loading
Loading