Longest Passage Without Traffic Lights (P)

x, n = map(int, input().split())
positions = list(map(int, input().split()))

lights = [0, x]
segments = [x]

def insert_light(p):
    left, right = 0, len(lights)
    while left < right:
        mid = (left + right) // 2
        if lights[mid] < p:
            left = mid + 1
        else:
            right = mid
    idx = left  
    left_light = lights[idx-1]
    right_light = lights[idx]
    
    old_segment = right_light - left_light
    segments.remove(old_segment)
    segments.append(p - left_light)
    segments.append(right_light - p)
    
    lights.insert(idx, p)
    
    return max(segments)

for p in positions:
    print(insert_light(p), end=' ')
print()