题目描述

Sherry 需要排序 $N$ 个整数，她只能使用双端队列。处理每个数时，可以：

1. 新建一个双端队列，并将当前数作为队列中唯一的数；
2. 将当前数放入已有队列的头部之前或尾部之后。

处理完所有数后，将各个队列按顺序连接起来可以得到非降序列。
求最少需要的双端队列数量。

输入格式

第一行一个整数 $N$，表示整数的个数。
接下来 $N$ 行，每行一个整数 $D_i$。

输出格式

一行，一个整数，表示最少需要的双端队列数。

6
3
6
0
9
6
3

2

数据规模与约定

对于全部的测试点，保证 $1 \leq N \leq 2 \times 10^5$，$D_i$ 在 int 范围内。