问题

高桥同学已经成年了，决定离开父母的身边独自生活。他想把卡车上的行李箱搬到新住处，但是如果房间的地板被行李箱填满，那么今天晚上高桥同学就无法铺床铺了。
为了解决这个问题，他决定不是一个箱子一个箱子地摊开，而是堆叠成一座山。然而，每个行李箱都有一定的重量，如果将比下面的箱子更重的箱子堆叠在上面，下面的箱子就会被压扁。

图：下面的箱子必须比上面的箱子重

按照从卡车运送的顺序，给出了每个行李箱的重量，你需要考虑如何堆叠行李箱，以避免压扁。然后，求出堆叠的山的最小数量。

---

输入

输入从标准输入中按以下格式给出。$N$ $w_1$ $w_2$ : : $w_N$

• 输入有 $N+1$ 行。
• 第 $1$ 行包含一个整数 $N(1≦N≦50)$，表示行李箱的数量。
• 从第 $2$ 行开始的 $N$ 行，每行包含一个整数 $w_i(1≦w_i≦100,000)$，表示第 $i$ 个要搬运的行李箱的重量。

输出

按顺序搬运行李箱，将上面的行李箱放在下面的行李箱上，并确保上面的行李箱与下面的行李箱重量相等或更轻。将能够形成的行李箱山的最小数量输出到标准输出中，一行输出。
最后要输出换行符。

---

输入例子 1

5
4
3
1
2
1

输出例子 1

2

• 如果按照下图的顺序堆叠，可以形成两座行李箱山。
• 无法将第 $3$ 个行李箱上面再叠加一个重量为 $2$ 的行李箱，因此无法将其归为一座山，最小值为 $2$。

---

输入例子 2

7
93
249
150
958
442
391
25

输出例子 2

3

• 如果按照下图的形式堆叠，可以得到 $3$ 座山。

更正：下图中的重量为225的行李箱应为25，对此表示歉意。

---

输入例子 3

4
100
100
100
100

输出例子 3

1

• 相同重量的行李箱可以堆叠在一起，因此可以形成 $1$ 座山。

---

输入例子 4

6
5
10
15
20
25
30

输出例子 4

6

• 由于没有一个行李箱可以叠加到前面搬运的行李箱上，所以无法叠加行李箱。
• 因此，最小值为 $6$。

---

输入例子 5

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

输出例子 5

6

• 如果按照下图的堆叠方式，可以得到最小数目。

---

来源

ARC 006

---