Hide

Problem D
Straights

In poker, a straight is a continuous sequence of cards, in this case of any length. Your friend John makes up a game called straights which is played with $N$ cards with numbers that may repeat, between $1$ and $10^4$. In order to win, you must get rid of all of your cards in as little turns as possible. The only way to put down more than $1$ card at a time is if the cards are strictly in descending or ascending order.

For example, given eight cards with the numbers: 1 8 3 6 5 7 2 1, the minimum number of turns to get rid of all of your cards would be: 3 because you would have 2 straights: 1 2 3 and 5 6 7 8 and a single card: 1 left over.

Can you find the minimum number of turns required for you to win?

Input

Input consists of two lines. The first contains the number of cards that you are given $N$ ($1 \leq N \leq 10^4$). The second line consists of $N$ space separated integers each with a value between $1$ and $10^4$.

Output

Output the minimum number of turns to win.

Sample Input 1 Sample Output 1
8
1 8 3 6 5 7 2 1 
3

Please log in to submit a solution to this problem

Log in