配点: 点
分岐のない 本の道のうえに, から までの番号のついた, 個の場と呼ばれる地点が順に並んでいます.
場 と場 とは 離れています.
MojaMoja 君は現在,既に を所持していますが,更に資産を増やしたいと思っています.
そこで,次のようなゲームに参加することにしました:
適切に馬を改造することによって「『報酬として得る金額』から『そのための馬の改造に費やした金額』を引いた差額」(利益) を正とすることができるような の選び方は何通りあるでしょうか?
求めてください.
各テストケースの入力は,それぞれ以下の形式で与えられる:
答えを出力せよ.
1 5 3 7 9 5 4 3 1 2 3
2
のとき,可能です.
たとえば を選んだとします.
を掛けて馬を改造し, で走れるようにすると,場 から場 までは ありますから, 以内(ちょうど)に到達することが可能です.
また,場 から 場 までを時間内に移動できた場合,報酬として を得ることができるので,これから改造に用いた を引いても,利益として が残ります.
したがって は満たします.
たとえば や の場合,どのように馬を改造しても正の利益を得ることはできません. (報酬を得るためには, 以内に移動を完了する必要があることに注意してください.)