Deque Sort 2

Time limit1sMemory limit256 MB

Summary

Place each number at the front or back of an existing deque or into a new one so the deques join into ascending order with the fewest deques.

Level: Medium6 of 10
Topics: Dynamic programming, Sorting, Intervals
Solved: No attempts yet

Problem

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.

Pick one of the deques you already made and put the number at its front.
Pick one of the deques you already made and put the number at its back.
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.

Input

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.

Output

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

Hint

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.

Examples3

Example 1
Input
```
6
3
6
0
9
5
4
```
Expected output
```
2
```
Example 2
Input
```
7
4
1
7
2
6
3
5
```
Expected output
```
3
```
Example 3
Input
```
2
5
-5
```
Expected output
```
1
```