Deque Sort

Time limit2sMemory limit128 MB

Summary

Given N integers in input order, assign each to a deque (front, back, or new deque) to minimize the number of deques whose concatenation can be sorted nondecreasing.

Level: Medium7 of 10
Topics: Greedy, Binary search, Sorting, Array
Solved: No attempts yet

Problem

A deque is a data structure that allows elements to be inserted or removed at both the front and the back.

You are given N integers in order. You must process them from the first integer to the last, and for each integer choose exactly one of the following operations.

Insert it at the front of an existing deque.
Insert it at the back of an existing deque.
Create a new deque and put it there.

After all integers have been inserted, the deques should be concatenated in some order so that the resulting sequence is in nondecreasing order. Find the minimum number of deques needed.

Input

The first line contains the number of integers N. N is a positive integer not greater than 1,000.

Each of the next N lines contains one integer. Every integer is between -1,000 and 1,000 inclusive, and values may be repeated.

Output

Print the minimum number of deques needed so that the deques can be concatenated into nondecreasing order.

Examples3

Example 1
Input
```
6
3
6
0
9
5
4
```
Expected output
```
2
```
Example 2
Input
```
10
50
45
55
60
65
40
70
35
30
75
```
Expected output
```
1
```
Example 3
Input
```
10
0
2
1
4
3
6
5
8
7
9
```
Expected output
```
5
```