C - Chokutter Addiction Editorial /

Time Limit: 2 sec / Memory Limit: 1024 MiB

配点 : 300 点

問題文

AtCoder 社は時刻 0 に始業し時刻 T に終業します。 時刻 t と時刻 t+1 との間隔は 1 秒です。
高橋君は AtCoder 社の業務時間中に SNS の chokutter を以下の規則で見ます。

  • 始業と同時に chokutter を開く。
  • 青木君が高橋君のデスクの後ろを通りかかった瞬間に chokutter を開いていた場合、直ちに chokutter を閉じる。
  • 高橋君は、 chokutter を時刻 t に閉じると、時刻 t+100 に必ず chokutter を開く。

始業から終業までに N 回青木君が高橋君のデスクの後ろを通りかかっており、そのうち i 回目は時刻 A_i でした。
始業から終業までに、高橋君は合計で何秒 chokutter を見ていましたか？
なお、 高橋君が chokutter を開いた瞬間に青木君がデスクの後ろを通りかかることはありませんでした。

制約

  • 入力は全て整数
  • 0 \le N \le 3 \times 10^5
  • 1 \le A_1 < A_2 < \dots < A_N \le T \le 10^9
  • 高橋君が chokutter を開いた瞬間に青木君がデスクの後ろを通りかかることはない

入力

入力は以下の形式で標準入力から与えられる。

N T
A_1 A_2 \dots A_N

出力

答えを出力せよ。

入力例 1

5 700
100 150 300 350 700

出力例 1

500
  • 時刻 0 に高橋君は chokutter を開きます。
  • 時刻 100 に青木君が高橋君のデスクの後ろを通りかかり、高橋君は直ちに chokutter を閉じます。
  • 時刻 150 に青木君が高橋君のデスクの後ろを通りかかりますが、高橋君はこの時点で chokutter を開いていません。
  • 時刻 200 に高橋君は再び chokutter を開きます。
  • 時刻 300 に青木君が高橋君のデスクの後ろを通りかかり、高橋君は直ちに chokutter を閉じます。
  • 時刻 350 に青木君が高橋君のデスクの後ろを通りかかりますが、高橋君はこの時点で chokutter を開いていません。
  • 時刻 400 に高橋君は再び chokutter を開きます。
  • 時刻 700 に青木君が高橋君のデスクの後ろを通りかかり、高橋君は直ちに chokutter を閉じます。

高橋君は、合計で 500 秒間 chokutter を見ていました。

入力例 2

0 1000000000

出力例 2

1000000000

青木君が高橋君のデスクの後ろを通りかかることがない場合もあります。

入力例 3

10 1234
395 424 588 745 773 863 910 958 1102 1195

出力例 3

734

Score : 300 points

Problem Statement

AtCoder Inc. starts work at time 0 and ends work at time T. The interval between time t and time t+1 is 1 second.
Takahashi-kun views the SNS chokutter during AtCoder Inc.'s business hours according to the following rules:

  • He opens chokutter at the same time as work starts.
  • If chokutter is open at the moment Aoki-kun passes behind Takahashi-kun's desk, he immediately closes it.
  • If Takahashi-kun closes chokutter at time t, he always opens it at time t+100.

From the start to the end of work, Aoki-kun passed behind Takahashi-kun's desk N times, with the i-th time being at time A_i.
From the start to the end of work, for how many seconds in total was Takahashi-kun viewing chokutter?
Aoki-kun never passed behind the desk at the moment when Takahashi-kun opened chokutter.

Constraints

  • All input values are integers.
  • 0 \le N \le 3 \times 10^5
  • 1 \le A_1 < A_2 < \dots < A_N \le T \le 10^9
  • Aoki-kun never passes behind the desk at the moment when Takahashi-kun opens chokutter.

Input

The input is given from Standard Input in the following format:

N T
A_1 A_2 \dots A_N

Output

Output the answer.

Sample Input 1

5 700
100 150 300 350 700

Sample Output 1

500
  • At time 0, Takahashi-kun opens chokutter.
  • At time 100, Aoki-kun passes behind Takahashi-kun's desk, and Takahashi-kun immediately closes chokutter.
  • At time 150, Aoki-kun passes behind Takahashi-kun's desk, but Takahashi-kun does not have chokutter open at this time.
  • At time 200, Takahashi-kun opens chokutter again.
  • At time 300, Aoki-kun passes behind Takahashi-kun's desk, and Takahashi-kun immediately closes chokutter.
  • At time 350, Aoki-kun passes behind Takahashi-kun's desk, but Takahashi-kun does not have chokutter open at this time.
  • At time 400, Takahashi-kun opens chokutter again.
  • At time 700, Aoki-kun passes behind Takahashi-kun's desk, and Takahashi-kun immediately closes chokutter.

Takahashi-kun was viewing chokutter for a total of 500 seconds.

Sample Input 2

0 1000000000

Sample Output 2

1000000000

There may be cases where Aoki-kun never passes behind Takahashi-kun's desk.

Sample Input 3

10 1234
395 424 588 745 773 863 910 958 1102 1195

Sample Output 3

734