Minimum Number of Deques

Sherry faces a difficult problem. She has \(N\) integers \(a_1,a_2,\dots,a_N\) with \(1 \le N \le 200000\) that need to be sorted. She only has some double‐ended queues (deques) at her disposal.

The numbers are processed in order from 1 to \(N\). For each number \(x\) she can do one of the following:

1. Create a new deque containing only \(x\).
2. Insert \(x\) at the beginning (head) or the end (tail) of an existing deque.

After processing all numbers, Sherry will concatenate the deques in some order (without changing the internal order of any deque) so that the resulting sequence is non‐decreasing.

Your task is to determine the minimum number of deques needed so that, if Sherry processes the numbers optimally, the final concatenated sequence will be non‐decreasing.

Note: In order for a deque to be used in the final concatenation, its internal sequence must be non‐decreasing. Hence, when inserting a new number \(x\), it can only be inserted at the tail if \(x\) is no smaller than the current last element, or at the head if \(x\) is no larger than the current first element.

Hint: A greedy strategy can be applied. For each new number \(x\):

• If there exists a deque with tail value \(R\) such that \(R \le x\), then append \(x\) to the tail of the deque having the maximum such \(R\) (i.e. the one that is as large as possible while \(\le x\)).
• Otherwise, if there exists a deque with head value \(L\) such that \(L \ge x\), then insert \(x\) at the head of the deque having the smallest such \(L\).
• If neither operation is possible then create a new deque containing \(x\).

The minimum number of deques required is the number of deques created during an optimal processing.

inputFormat

The first line contains an integer \(N\) \((1 \le N \le 200000)\), the number of integers. The second line contains \(N\) integers \(a_1,a_2,\dots,a_N\) separated by spaces.

outputFormat

Output a single integer representing the minimum number of deques needed.

sample

3
3 1 2

2