Practice Greedy algorithms with the exercise "Magic stones"

Learning Opportunities

This puzzle can be solved using the following concepts. Practice using these concepts and improve your skills.

Greedy algorithms

Statement

Goal

You have a number N of magic stones each of which has a level with a positive integer value.

The stones are very heavy and cumbersome to carry around.

Luckily you can use your magic powers to combine two stones of level i to form a single stone of level i+1.

Use your power to minimise the number of stones that you have.

Input

Line 1: An integer N for the number of magic stones you have.
Line 2: N space separated integer values

Output

Line 1: The minimum number of stones you can have.

Constraints

0 < N < 1000

Example

Input

2
1 1

Output

Solve it

A higher resolution is required to access the IDE