006 - スプリットタイム
時間制限 1 秒 / メモリ制限 64 MB / 得点 6 / x 10 /
問題
カクマ君は体力測定の持久走に参加した。カクマ君は運動場のトラックを時刻0に走り始めて、トラックを周回する。この持久走では、スタートから1周、2周、…、$N$周したときの目標経過時間(スプリットタイム)がそれぞれ決められていて、カクマ君はそれらにしたがって以下のように走らなければならない。
- $i$周した時の目標経過時間より早くカクマ君が$i$周したときは、$i$周走り終えた所で目標経過時間になるまで立ち止まる。目標経過時間になった瞬間に持久走を再開し、$i+1$周目を走り始める。
- それ以外の場合は、カクマ君は立ちどまらずに走り続ける。
カクマ君が2周続けて目標経過時間よりも遅れて周回したとき持久走は終了となる。2周続けて目標経過時間よりも遅れて周回することなくトラックを$N$周できたときにも、持久走は終了となる。目標経過時間に遅れずに周回した回数がカクマ君の記録になる。たとえば、1周、2周、4周したときには遅れずに周回し、3周、5周、6周したときには遅れて周回したなら、6周したところで終了し、記録は3回になる。
カクマ君がトラックを1周するのにかかる時間と、各周回後のスタートからの目標経過時間が与えられたとき、カクマ君の記録を求めるプログラムを作成せよ。ただし、カクマ君がトラックを1周するのにかかる時間はつねに一定とする。
入力
入力は以下の形式で標準入力から与えられる。
$N T$ $a_1 a_2...a_N$
1行目に、周回の最大数$N(1 \leq N \leq 100)$とカクマ君がトラックを1周するのにかかる時間$T(1 \leq T \leq 1,000,000)$が与えられる。2行目に、$i$周した時の目標経過時間$a_i(1 \leq a_i \leq 1,000,000,000)$が与えられる。ただし、a_i < ai+1である。
出力
カクマ君の記録を1行に出力する。
入出力例
入力例1
6 10 12 25 32 40 53 61
出力例1
2
カクマ君は10分で周回するので、最初に1周した後2分立ち止まり、スタートから12分経過後に2周目を走り始める。2周するのはスタートから22分経過後なので、3分立ち止まって25分経過後に3周目を走り始める。しかし、スタートから32分経過するまでに3周することはできず、そのまま走り始めても40分経過するまでに4周できないので4周で終了する。目標経過時間に遅れず周回したのは、それぞれ1周、2周したときなので、カクマ君の記録は2回である。
入力例2
7 8 10 20 25 38 43 52 68
出力例2
3
最初の2周は目標経過時間に遅れず、スタートから20分経過後に3周目を走り始める。25分経過までには3周できないが、そのまま走り続けて38分経過するまでに4周できる。しかし、38分経過後から5周目を走り始めると、スタートから43分経過するまでには5周できず、そのまま走り続けても52分経過するまでには6周できないので、6周で終了となる。目標経過時間に遅れず周回したのは、それぞれ1周、2周、4周したときなので、カクマ君の記録は3回である。