题目描述

某玻璃瓶工厂收到一份订单，需要生产 $n$ 个钢化玻璃瓶。这些瓶子并不相同：编号为 $i$ 的瓶子必须在钢化炉中恰好停留 $t_i$ 秒。

工厂有若干相同的钢化炉，具有如下特性：

• 每个炉子容量无限；
• 由于只有一个入口/出口，炉子按 LIFO 规则工作：最后放入的瓶子必须最先取出；
• 放入一个瓶子需要 $1$ 秒，该秒结束后瓶子开始钢化；
• 取出一个瓶子需要 $1$ 秒，该秒结束后瓶子的钢化过程结束；
• 一旦从某个炉子中取出过瓶子，就不能再往这个炉子里放入新的瓶子；
• 炉子使用后不能立刻重复使用，因为需要清洁并重新装填燃料。

工厂可以按任意顺序处理瓶子。

请计算完成订单至少需要多少个钢化炉。

输入格式

第一行输入整数 $n$。

第二行输入 $n$ 个整数 $t_i$，表示每个瓶子所需钢化时间。

输出格式

输出一个整数，表示所需炉子的最小数量。

数据范围

• $1\le n\le 200000$
• $1\le t_i\le 10^9$

子任务

样例 1

输入

2
1 2

输出

2

解释

这就是题面中给出的例子，两个瓶子无法放在同一个炉中完成。

样例 2

输入

3
3 6 1

输出

1

解释

只需要一个炉子，放入顺序可以是瓶子 $1,0,2$。

样例 3

输入

5
1 2 4 3 2

输出

3