Problem Description

Sherry is facing a tricky problem: there are $N(1 \le N \le 200000)$ integers that need to be sorted.

The only tools Sherry can use are several deques.

She must process these $N$ numbers in order from $1$ to $N$. For each number, Sherry can do one of the following:

1. Create a new deque and put the current number as the only element in this deque.

2. Put the current number into an existing deque, either before the front or after the back.

After all numbers are processed, Sherry can connect these deques in some order to obtain a non-decreasing sequence.

Please find the minimum number of deques needed.

Input Format

The first line contains an integer $N$, representing the number of integers.

The next $N$ lines each contain an integer $D_i$, representing the integer to be processed.

Output Format

Output one integer, representing the minimum number of deques needed.

6
3
6
0
9
6
3

2

Hint

Constraints: $1 \le N \le 200000$，$-2^{31} \le D_i < 2^{31}$。

Translated by ChatGPT 5