In what concerns the continuous evaluation solving exercises grade during the semester, you should submit until 23:59 of December 7th
(this exercise will still be available for submission after that deadline, but without couting towards your grade)
[to understand the context of this problem, you should read the class #08 exercise sheet]

[AED048] Traffic Lights

This problem is an adapted Mooshak version of a CSES problem.

There is a street of length X whose positions are numbered 0, 1, ..., X. Initially there are no traffic lights, but N sets of traffic lights are added to the street one after another.

The Problem

Your task is to calculate the length of the longest passage without traffic lights after each addition.

Input

The first input line contains two integers X and N: the length of the street and the number of sets of traffic lights.

Then, the next line contains N integers P₁, P₂, ..., P_N)​: the position of each set of traffic lights. Each position is distinct.

Output

Print the length of the longest passage without traffic lights after each addition. There should be a single space between each number in the output (but no space at before the first numberor after the last number.

Constraints

8 3
3 6 2

5 3 3

Explanation of Example Input

• After the first traffic light is added to position 3, the longest passage without traffic lights is [3,8], with length 5:
  
• After the second traffic light is added to position 6, the longest passage without traffic lights is [0,3] or [3,6], both with length 3:
  

• After the third traffic light is added to position 2, the longest passage without traffic lights is [3,6], with length 3:
  
  
  

  ---

  Algorithms and Data Structures (L.EIC011) 2024/2025
  DCC/FCUP & DEI/FEUP - University of Porto

  ---