問題文

スキーが大好きなタカシくんは、ニコニコスキー場でリフト係のアルバイトを始めました。 このスキー場には搬器（いす）1 台あたりの定員が 4 人であるリフトが 1 基あり、ここにスキー客が 1 人から 4 人までのグループで並びに来ます。

ある日、リフトの待ち行列が長くなったことに困ったタカシくんは、スキー客にリフトの相乗りをしてもらおうと考えました。 タカシくんは、搬器が 1 台乗り場に着くごとに以下のような手順でスキー客のグループをその搬器に案内することにしました。

• 最初に、待ち行列の先頭にいるグループを搬器に案内する。
• 現在の搬器に相乗りしても定員を超えないようなグループが存在する限り、そのようなグループを搬器に案内する。ただし、そのようなグループが複数存在する場合は、待ち行列での位置に関わらず、いずれのグループを案内しても構わない。

今、リフトには N グループのスキー客が並んでおり、待ち列の先頭から i (1 ≦ i ≦ N) 番目のグループは A_i 人のスキー客からなります。 タカシくんがうまくスキー客のグループを案内することによって、最短で何台目の搬器で今並んでいるグループをすべて運びきることができるかを求めて下さい。

制約

• 1≦N≦10^5
• 1≦A_i≦4

入力例 1

3
1
1
2

出力例 1

1

合計が 4 人以内であれば、タカシくんはグループを何組でも同じ搬器に案内することができます。

入力例 2

6
3
1
4
2
1
2

出力例 2

4

例えば以下のようにスキー客を案内すると 4 台の搬器で全てのグループを運びきることができます。

• 1 台目の搬器に 1 番目のグループと 5 番目のグループを案内する。
• 2 台目の搬器に 2 番目のグループと 4 番目のグループを案内する。
• 3 台目の搬器に 3 番目のグループを案内する。
• 4 台目の搬器に 6 番目のグループを案内する。