以下是来自日本的原始新闻PDF,已完整保存和染色。


可复制的 PDF 提取文本
2 最長の階段
問題
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 ≦k ≦n) がこの順で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 を満たす.
問題2-1
出力
出力ファイルのファイル名はoutput.txt である.
output.txt は1 行だけからなり,その1 行は出力する整数1 つだけを含む.
入出力の例
入出力の例1
例1 に対応する入出力は以下の通りである.
input.txt
7 5
6
2
4
7
1
output.txt
2
入出力の例2
例2 に対応する入出力は以下の通りである.
input.txt
7 5
6
2
0
4
7
output.txt
4
問題2-2