Deque Sort 2

A deque is like a queue, but you can insert and remove data at both the front and the back.

You are given $N$ numbers. Going from the first number to the last one in order, you must handle each number with one of these three actions.

1. Pick one of the deques you already made and put the number at its front.
2. Pick one of the deques you already made and put the number at its back.
3. Make a new deque and put the number in it.

After every number has been placed this way, you concatenate the deques in any order you like so that the whole sequence is in ascending order. The numbers inside a deque keep the order in which they are read from front to back. Write a program that finds the smallest number of deques you need.

The first line contains the count of numbers $N$. $N$ is a natural number not greater than 50. Each of the next $N$ lines contains one number. Every number is an integer between -1000 and 1000 inclusive, and no number is given twice.

Print the smallest number of deques needed on the first line.

When the numbers arrive in the order 3, 6, 0, 9, 5, 4, two deques are enough.

• Make a new deque and put 3 in it. Deque1: {3}
• Make a new deque and put 6 in it. Deque2: {6}
• Put 0 at the front of Deque1. Deque1: {0, 3}
• Put 9 at the back of Deque2. Deque2: {6, 9}
• Put 5 at the front of Deque2. Deque2: {5, 6, 9}
• Put 4 at the front of Deque2. Deque2: {4, 5, 6, 9}
• Attaching Deque2 after Deque1 gives 0, 3, 4, 5, 6, 9, which is in ascending order.