Given an array $a$ with $n$ elements, you can perform the following operation an infinite number of times: Choose an index $1 \le i \le n - 1$ such that $a_i = a_{i + 1}$, delete the two elements $a_i$ and $a_{i + 1}$, and replace them with an element with the value $a_i + 1$. Find the minimum possible length of the array $a$.

Input

• The first line contains a natural number $n \le 500$.
• The next line contains $n$ natural numbers of the array $a$, each $\le 1000$.

Output

• Print the minimum possible length of the array $a$.

Sample Test

Input:

7
3 3 4 4 4 3 3

Output:

2