AT_arc006_3.[ARC006C] 積み重ね

高桥君已经长大成人，决定离开父母独自生活。他需要把行李从卡车搬到新家的房间里，但如果把纸箱平铺在地板上，房间就会被纸箱占满，今晚他就无法铺床睡觉了。
因此，他决定不把纸箱一个个分开放，而是把纸箱适当地堆叠成若干堆。然而，每个纸箱都有一定的重量，如果把比下面纸箱更重的纸箱堆在上面，下面的纸箱就会被压坏。

图示：下面的纸箱必须比上面的纸箱重或相等。

现在，按照从卡车搬运的顺序，给出了每个纸箱的重量。请思考一种堆叠方式，使得不会压坏任何纸箱，并且堆叠出的纸箱堆的数量最少。请输出最少需要多少堆纸箱。

输入按以下格式从标准输入给出。

输入共 $N+1$ 行。

• 第 $1$ 行是一个整数 $N$，表示纸箱的数量，$1 \leq N \leq 50$。
• 接下来的 $N$ 行，第 $i+1$ 行给出第 $i$ 个搬运的纸箱的重量 $w_i$，$1 \leq w_i \leq 100,\!000$。

输出一行，表示最少需要的纸箱堆的数量。最后请输出换行符。

• 例如输入：

5
4
3
1
2
1

输出：

2

• 按照示例中的顺序堆叠，可以形成 $2$ 堆纸箱。

• 不能将第 $3$ 个纸箱后面的重量为 $2$ 的纸箱堆在它上面，因此无法只用 $1$ 堆，最少为 $2$ 堆。

• 例如输入：

7
93
249
150
958
442
391
25

输出：

3

• 如图所示，可以堆成 $3$ 堆。

• 说明：图中的 $225$ 应为 $25$，敬请谅解。

• 例如输入：

4
100
100
100
100

输出：

1

• 相同重量的纸箱可以堆叠，因此只需 $1$ 堆。

• 例如输入：

6
5
10
15
20
25
30

输出：

6

• 没有任何纸箱可以堆在前面搬运的纸箱上，因此每个纸箱都单独成堆，最少为 $6$ 堆。

• 例如输入：

15
3
1
4
1
5
9
2
6
5
3
5
8
9
7
9

输出：

6

• 如图所示，这样堆叠时堆的数量最少。

由 ChatGPT 4.1 翻译