문제 설명
충북이는 1부터 N까지의 정수가 각각 하나씩 적힌 N장의 카드와, 숫자가 적히지 않은 카드 하나를 가지고 있다. 충북이는 이들 N+1장의 카드 중, K개의 카드를 임의로 선택하여 일렬로 펼쳐놓았다.
이렇게 펼쳐진 K개의 카드에서, 충북이는 가능한 가장 긴 연속 정수열을 만들려고 한다.
연속 정수열이란, [1, 2, 3, 4]나 [7, 8, 9]처럼 숫자가 하나씩 늘어나는 정수열을 말한다.
충북이는 모든 카드를 선택하지 않을 수도 있으며, 카드의 순서를 바꿀 수도 있다.
또한, K개의 카드 중 숫자가 적히지 않은 카드가 있다면, 해당 카드에 1부터 N까지의 정수 중 하나를 적어서 해당 카드를 원하는 숫자 카드처럼 사용할 수도 있다.
충북이는 주어진 카드들에 최선의 전략을 사용하여, 충북이가 만든 연속 정수열의 길이를 최대화하려고 한다.
카드의 정보 N, K와 K장의 카드가 주어질 때, 충북이가 만들 수 있는 연속 정수열의 최대 길이를 구해보자.
입력 설명
첫 줄에 정수 N과 K가 공백을 사이에 두고 주어진다. N, K는 각각 숫자가 적힌 카드의 수와 펼쳐진 카드의 수를 의미한다.
다음 K개의 줄 중 i번째 줄에는 정수 ai가 주어진다. 이는 펼쳐진 카드 중 i번째 카드에 쓰인 숫자를 의미한다. 숫자가 적히지 않은 카드는 0으로 주어진다.
제한
-
1 ≤ N ≤ 100,000
-
1 ≤ K ≤ N
-
0 ≤ ai ≤ N
출력 설명
충북이가 만들 수 있는 연속 정수열의 최대 길이를 출력한다.