ACPC 2020 - Division 1


2020-11-14 10:00 AKST

ACPC 2020 - Division 1


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


Time remaining


Problem F

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 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 the minimum number of turns to win.

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