The Longest Staircase

Interview

Time limit1sMemory limit128 MB

Summary

Given k cards with distinct values 1 to n plus one blank card (0) you can set to any value, find the longest run of consecutive integers formable.

Level: Medium4 of 10
Topics: Sorting, Two pointers, Implementation
Solved: No attempts yet

Problem

There are $n$ cards, each showing a distinct integer from $1$ to $n$ , plus one blank card, for $n+1$ cards in total. Out of these $n+1$ cards, $k$ of them are given to you ( $1 \le k \le n$ ). On the blank card you may write any single integer from $1$ to $n$ .

Using only the given cards, you want to form the longest possible run of consecutive integers. Given the cards, write a program that prints the maximum length of a consecutive integer sequence that can be formed from them.

Input

The first line contains two integers $n$ ( $1 \le n \le 100000$ ) and $k$ ( $1 \le k \le n$ ), in this order, separated by a single space. Each of the next $k$ lines contains one integer describing the value on one of the $k$ given cards. The blank card is represented by $0$ .

Output

Print a single line containing one integer: the maximum length of a consecutive integer sequence that can be formed.

Examples2

Example 1
Input
```
7 5
6
2
4
7
1
```
Expected output
```
2
```
Example 2
Input
```
7 5
6
2
0
4
7
```
Expected output
```
4
```