Question
Garden rehabilitation
You’re building a fence for your garden. There is a long wooden beam marked from 0 to N (0, 1, 2,…, N). The carpenter makes K cuts on the beam. The ith cut is made at position pi. After each cut, you need to determine the length of the longest remaining piece of the beam.
Input
The first line of the input contains two space-separated integers N and K.
The second line of the input contains K space-separated integers.
Constraints
1 ≤ N ≤ 109
1 ≤ K ≤ 2x105
0 < pi < N
All pi are distinct
The second line of the input contains K space-separated integers.
Constraints
1 ≤ N ≤ 109
1 ≤ K ≤ 2x105
0 < pi < N
All pi are distinct
Output
Print the length of the longest remaining piece of the beam.
Example
Sample Input
8 3
2 6 3
Sample Output
6 4 3
Explanation
Initially, the length of the beam is 8. After the first cut at 2,
The beam is divided into two segments of length 2 and 6. So the longest segment is of length 6.
After the second cut at 6, the segments are 2, 4, 2. So, the longest segment is of length 4.
After the third cut, the segments are 2, 1, 3, 2. So, the longest segment is of length 3.
8 3
2 6 3
Sample Output
6 4 3
Explanation
Initially, the length of the beam is 8. After the first cut at 2,
The beam is divided into two segments of length 2 and 6. So the longest segment is of length 6.
After the second cut at 6, the segments are 2, 4, 2. So, the longest segment is of length 4.
After the third cut, the segments are 2, 1, 3, 2. So, the longest segment is of length 3.