#1932 · Lan truyền bí mật

Trong một buổi học ngoại khóa, n sinh viên ngồi thành một hàng ngang trong lớp và được đánh số từ 1 đến n. Các sinh viên có khả năng truyền thông tin cho sinh viên ngồi ngay bên cạnh mình trong 1 đơn vị thời gian:

• Sinh viên số i có thể truyền thông tin cho:

  • Sinh viên số i-1 (nếu tồn tại).
  • Sinh viên số i+1 (nếu tồn tại).

• Sinh viên số 1 chỉ có thể truyền thông tin cho sinh viên số 2.

• Sinh viên số n chỉ có thể truyền thông tin cho sinh viên số n-1.

Ban đầu, có m sinh viên được chỉ định (a_1, a_2, ..., a_m) đã biết trước một bí mật quan trọng. Nhiệm vụ của bạn là tính thời gian tối thiểu để tất cả sinh viên trong lớp đều biết được bí mật này.

• Dòng đầu tiên chứa hai số nguyên n và m (cách nhau bởi khoảng trắng):

  • n: Số lượng sinh viên trong lớp.
  • m: Số lượng sinh viên ban đầu biết bí mật.

• Dòng thứ hai chứa m số nguyên a_1, a_2, ..., a_m (cách nhau bởi khoảng trắng), biểu thị các vị trí của những sinh viên đã biết bí mật ban đầu.

In ra thời gian tối thiểu (tính bằng đơn vị thời gian) để tất cả sinh viên trong lớp đều biết được bí mật.

• 2 ≤ n ≤ 100000 (tối đa 100,000 sinh viên).
• 1 ≤ m ≤ n.
• 1 ≤ a_i ≤ n.
• Các giá trị ai là duy nhất và được sắp xếp tăng dần.