配点 : 400 点
問題文
热爱滑雪的 Takashi 开始在 Niconico 滑雪场兼职做电梯服务员。 这个滑雪场没有椅子。1 每辆车的容量 4 人力电梯 1 这里有滑雪者。 1 来自人 4 人们成群结队地排队。
有一天,Takashi-kun 担心缆车要排很长的队,所以他决定让滑雪者共用缆车。 隆君有一个载体。 1 我们决定在每次滑雪者到达平台时都按照以下程序引导他们前往承运人。
- 首先,队列前面的队伍被引导到车厢。
- 只要有不超过载客量的团体,即使他们共用当前车厢,也会将此类团体引导至该车厢。但是,如果有多个此类组,您可以引导任何组,无论它们在队列中的位置如何。
现在在电梯上 N 一群滑雪者正在排队,从队列的前面开始。 i (1 ≦ i ≦ N) 组是 A_i 由滑雪者组成。 如果隆君巧妙地引导这群滑雪者,找出有多少运输车可以在最短的时间内运送目前排队的所有队伍。
制約
- 1≦N≦10^5
- 1≦A_i≦4
入力
输入是按以下格式从标准输入给出的。
N A_1 A_2 : A_N
出力
计算运送当前排队的所有组所需的运输工具数量。 1 行。在末尾输出换行符。
入力例 1
3 1 1 2
出力例 1
1
总计为 4 Takashi-kun 可以将任意数量的团体引导到同一载体,只要它们在团体规模之内。
入力例 2
6 3 1 4 2 1 2
出力例 2
4
例如,如果您按如下方式指导滑雪者: 4 所有团体都可以使用一辆运输工具运输。
- 1 至第二个运营商 1 第组和 指导第 5 组。
- 2 至第二个运营商 2 第组和 指导第 4 组。
- 3 至第二个运营商 3 组。
- 4 至第二个运营商 6 组。