ACPC 2020 - Division 1

Start

2020-11-14 10:00 AKST

ACPC 2020 - Division 1

End

2020-11-14 15:00 AKST
The end is near!
Contest is over.
Not yet started.
Contest is starting in -10 days 19:10:26

Time elapsed

5:00:00

Time remaining

0:00:00

Problem F
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 different 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