Deque Sort

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.

1. Insert it at the front of an existing deque.
2. Insert it at the back of an existing deque.
3. 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.

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.

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