J - K-Ba

配点： 点

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

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

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

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

• 入力はすべて整数

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

答えを出力せよ．

1
5 3
7 9 5 4
3 1 2 3

2

のとき，可能です．

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

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