链接: https://cses.fi/problemset/task/1073

板块: Sorting and Searching

时限: 1.00 s ｜ 内存: 512 MB

题目描述

给定 $n$ 个立方体，按特定顺序排成一列，你的任务是用它们搭建塔。每当两个立方体上下叠放时，上面的立方体必须比下面的小。

你必须按给定顺序处理立方体。对于每个立方体，你可以把它放在某个已有塔的顶部，也可以开始一座新塔。最少需要搭建多少座塔？

输入

第一行包含一个整数 $n$：立方体的数量。

下一行包含 $n$ 个整数 $k_1,k_2,\ldots,k_n$：每个立方体的大小。

输出

输出一个整数：最少的塔的数量。

数据范围

$1 \le n \le 2 \cdot 10^5$ $1 \le k_i \le 10^9$

样例输入

5
3 8 2 1 5

样例输出

2