第3回 ドワンゴからの挑戦状 予選

C - スキーリフトの相乗り


Time limit時間制限 : 2.525sec / Memory limitメモリ制限 : 252.525MB

配点 : 400

問題文

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

ある日、リフトの待ち行列が長くなったことに困ったタカシくんは、スキー客にリフトの相乗りをしてもらおうと考えました。 タカシくんは、搬器が 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 人以内であれば、タカシくんはグループを何組でも同じ搬器に案内することができます。


入力例 2

6
3
1
4
2
1
2

出力例 2

4

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

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

Submit提出する