D - 壊れた電車
Editorial
/
Time Limit: 2 sec / Memory Limit: 256 MB
問題文
高橋鉄道では、N 両編成の電車の一部が壊れてしまったため、M 人の整備士が点検をすることになりました。
i 人目の整備士ははじめ、X_i 両目の車両にいます。それぞれの整備士は、今いる車両を点検することと、隣の車両に移動することができます。車両の点検には時間はかかりませんが、隣の車両に移動するには 1 分かかります。
全ての車両を少なくとも 1 人の整備士が点検した状態になると点検作業は終了となります。点検作業は最短何分で終了させることができるでしょうか。
入力
入力は以下の形式で標準入力から与えられる。
N M X_1 X_2 : X_M
- 1 行目には、2 つの整数 N (1 ≦ N ≦ 10^9), M (1 ≦ M ≦ 10^5, M ≦ N) が空白区切りで与えられる。これは、電車が N 両の車両からなり、整備士が M 人いることを表す。
- 2 行目からの M 行には、整備士の情報が与えられる。このうち i (1 ≦ i ≦ M) 行目には、整数 X_i (1 ≦ X_i ≦ N) が与えられる。これは、i 人目の整備士がはじめ X_i 両目の車両にいることを表す。ただし、X_i は全て相異なることが保証される。また、整備士の情報は 1 両目の車両に近い順に与えられる、つまり X_j < X_{j+1} (1 ≦ j ≦ M-1) であることが保証される。
部分点
この問題には部分点が設定されている。
- N ≦ 100 を満たすデータセットに正解した場合は、20 点が与えられる。
- N ≦ 500,000 を満たすデータセットに正解した場合は、上記とは別に 60 点が与えられる。
- 追加の制約のないデータセットに正解した場合は、上記とは別に 20 点が与えられる。
出力
点検作業にかかる時間の最小値を分単位で 1 行に出力せよ。出力の末尾に改行を入れること。
入力例1
17 5 1 5 10 15 16
出力例1
3
下の図のように整備士が移動すれば 3 分で点検作業を終了させることができます。
入力例2
66 10 8 9 16 23 37 47 51 52 53 64
出力例2
8