美食の要素は料理、時期、相手。そして……

ハルナ

ご機嫌よう、ハルナです。新年のあの出来事から、もう一週間が経ちましたね。

先週のことをまとめますと、今回の新年の騒動は、閉店の危機に瀕した小さな食堂「スズメ亭」を守るため、私たち美食研究会が美味しいものを食べたいという一心で、巨大流通企業「ニャオフード」と対峙したお話でした。ニャオフードがスズメ亭を買収してチェーン店にしようとしたため、私たちはお店の命運を懸けた料理勝負の提案を受け入れました。その過程でグルメヘルメット団まで巻き込まれ、街の一角が丸ごと大騒ぎになりましたわ。最終的に一度の勝負を経て、スズメ亭は元の姿を守ったまま存続することができました。そして今日、私たちはこうした隠れた名店をもっと探し、世に広めるという素晴らしい目標を得たのです。

私たち美食研究会が厳選した食堂は全部で $N$ 軒あり、$i$ 番目の食堂の美味しさは $A_i$ だと記録してあります。$1$ 番から $N$ 番まで、順番に訪れるツアーを企画するつもりです。もし気に入らない食堂があれば……事前に爆破しておきましょう。$N$ 軒の中から気に入らない食堂をいくつか選んで爆破し、残った食堂は元の順番を保って詰めて訪れます。ああ、ツアーで食事をしないなどあり得ませんから、少なくとも二軒は残さなければなりませんね。 残った食堂を順に訪れながら、次へ進むほど美味しくなるかどうかを見ていきます。

そうそう、いくつかの食堂は風紀委員会が守っているかもしれませんが……幸い、その情報はすでに入手済みです。$S_i=\texttt{0}$ なら、$i$ 番の食堂は爆破して構いません。ですが、$S_i=\texttt{1}$ なら、残念ながら爆破することはできません。せっかくの美食ツアーを台無しにはしたくありませんもの。ふふふ。

続けて訪れる二軒を一組とし、次の食堂が前の食堂より美味しければ、その美味しさの差だけ気分が良くなります。逆に、次の食堂の方が美味しくなければ、その分だけ気分が下がります。残った食堂をすべて順に訪れる間の、隣り合う二軒の美味しさの差分を合計した値を満足度と呼びましょうか。私たちが得られる満足度の最大値が気になりますわね。それでも、できるだけ多彩な味を楽しみたいので、満足度が最大となるツアーの中で爆破する食堂の数は最小にしたいところです。

満足度を厳密に定義するなら……爆破後に残った $M$ 軒のうち、$i$ 番目の食堂の美味しさを $B_i$ としましょう。すると満足度は、

となります。

さあ、先生。満足度の最大値と、そのとき爆破すべき食堂の最小数を求めましょう。

すべてのテストケースにわたる $N$ の合計は $200\,000$ を超えない。

実行時間制限

1000 ms

メモリ制限

1024 MB

チェッカー

CUSTOM