配点:

問題文


分岐のない 本の道のうえに, から までの番号のついた, 個のと呼ばれる地点が順に並んでいます.
と場 とは 離れています.

MojaMoja 君は現在,既に を所持していますが,更に資産を増やしたいと思っています.
そこで,次のようなゲームに参加することにしました:

  • を満たす 整数 を選び,馬に乗って場 から 場 へ移動する.
  • 馬の走る速さは,はじめ であり, を支払うごとに ずつ速く走れるように改造できる.すなわち, を払うことで で走ることができるようになる.( は非負整数)
  • 以内に場 から場 へ移動することができれば,ゲームをクリアしたとみなされる.
  • ゲームをクリアしたとき,場 と場 との間を通過したごとに,報酬として を得る.
  • 以内に到達できなかった場合の報酬はない.

適切に馬を改造することによって「『報酬として得る金額』から『そのための馬の改造に費やした金額』を引いた差額」(利益) を正とすることができるような の選び方は何通りあるでしょうか?
求めてください.

制約


  • 入力はすべて整数

入力


各テストケースの入力は,それぞれ以下の形式で与えられる:



出力


答えを出力せよ.

サンプル


入力例1
1
5 3
7 9 5 4
3 1 2 3
出力例1
2

のとき,可能です.

たとえば を選んだとします.
を掛けて馬を改造し, で走れるようにすると,場 から場 までは ありますから, 以内(ちょうど)に到達することが可能です.
また,場 から 場 までを時間内に移動できた場合,報酬として を得ることができるので,これから改造に用いた を引いても,利益として が残ります.
したがって は満たします.

たとえば の場合,どのように馬を改造しても正の利益を得ることはできません. (報酬を得るためには, 以内に移動を完了する必要があることに注意してください.)

提出


Go (1.14)