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 翻译