P10465 Deque

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.

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 one integer, representing the minimum number of deques needed.

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