Longest Steps

Time Limit : 1 sec, Memory Limit : 65536 KB

最長の階段

問題

1 から n までの整数がそれぞれ 1 つずつ書かれた n 枚のカードと,1 枚の白紙の カードがある.これら n + 1 枚のカードの内,k 枚のカードが与えられる.ただし, 1 ≤ k ≤ n である.白紙のカードには 1 から n までの整数を 1 つ書くことができ る.与えられたカードだけで,できるだけ長い連続した整数列を作りたい.

与えられるカードが入力されたときに, 与えられたカードから作ることができる連 続した整数列の最大長を出力するプログラムを作成せよ.

例1

n = 7, k = 5 とする.6, 2, 4, 7, 1 のカードが与えられたとき,このカードを使っ て作れる連続した整数列のうち最長のものは 1, 2 であり,その長さは 2 である.

例2

n = 7, k = 5 とする.6, 2, 4, 7 と白紙のカードが与えられたとき,このカードを 使って作れる連続した整数列のうち最長のものは,白紙のカードに 5 を書くことに よってできる 4, 5, 6, 7 であり,その長さは 4 である.

入力

入力ファイルのファイル名は input.txt である.

1 行目には,2 つの整数 n (1 ≤ n ≤ 100000) と k (1 ≤ kn) がこの順で 1 つの 空白を区切りとして書かれている.続く k 行には整数が 1 つずつ書かれており,与 えられる k 枚のカードに書かれている整数を表している.白紙のカードは 0 で表さ れる.

採点用データのうち, 配点の 40% 分は 1 ≤ n ≤ 1000, 1 ≤ k ≤ 500 を, 配点の 20% 分は 1 ≤ n ≤ 60000, 1 ≤ k ≤ 50000 を. 配点の 40% 分は 1 ≤ n ≤ 100000, 1 ≤ k ≤ 100000 を満たす.

出力

出力ファイルのファイル名は output.txt である. output.txt は 1 行だけからなり,その 1 行は出力する整数 1 つだけを含む.

入出力の例

input.txt

7 5
6
2
4
7
1

output.txt

2

上記問題文と自動審判に使われるデータは、情報オリンピック日本委員会が作成し公開している問題文と採点用テストデータです。

Notes on Submission

標準入出力を行うプログラムを作成して下さい.

上記形式で複数のデータセットが与えられます. データセットの終わりは2つのゼロを含む行で示されます.

Sample Input

7 5
6
2
4
7
1
7 5
6
2
0
4
7
0 0

Sample Output

2
4

Source: 7th Japanese Olympiad in Informatics , 2007-02-12
http://www.ioi-jp.org/