가장 긴 계단

면접 대비

시간 제한1초메모리 제한128 MB

요약
1부터 n까지 서로 다른 값이 적힌 카드 k장과 임의의 수를 적을 수 있는 빈 카드(0) 한 장이 주어질 때, 만들 수 있는 가장 긴 연속 정수 구간의 길이를 구한다.
난이도

보통10점 중 4점

유형
정렬, 투 포인터, 구현
정답자
아직 제출이 없습니다

문제

11부터 nn까지의 정수가 하나씩 적힌 카드 nn장과, 아무것도 적히지 않은 백지 카드 11장이 있다. 즉 카드는 모두 n+1n+1장이다. 이 n+1n+1장 중에서 kk장의 카드가 주어진다(1≤k≤n1 \le k \le n). 백지 카드에는 11부터 nn까지의 정수 중 하나를 적을 수 있다.

주어진 카드만으로 가능한 한 긴 연속된 정수의 나열을 만들고 싶다. 주어진 카드가 입력되었을 때, 그 카드들로 만들 수 있는 연속된 정수열의 최대 길이를 출력하는 프로그램을 작성하여라.

입력

첫째 줄에 두 정수 nn (1≤n≤1000001 \le n \le 100000)과 kk (1≤k≤n1 \le k \le n)이 공백 하나를 사이에 두고 이 순서대로 주어진다. 이어지는 kk개의 줄에는 각각 정수가 하나씩 주어지며, 이는 주어진 kk장의 카드에 적힌 정수를 나타낸다. 백지 카드는 00으로 나타낸다.

출력

한 줄에 정수 하나, 곧 만들 수 있는 연속된 정수열의 최대 길이를 출력한다.

예제2

  1. 예제 1

    입력
    7 5
    6
    2
    4
    7
    1
    
    예상 출력
    2
    
  2. 예제 2

    입력
    7 5
    6
    2
    0
    4
    7
    
    예상 출력
    4