Grab Your Seat!

Xem PDF

Điểm: 400 (p) Thời gian: 1.0s Bộ nhớ: 256M Input: bàn phím Output: màn hình

Bờm thực hiện được ước mơ thời thơ ấu của mình là được mời vào Ban Tổ chức hội nghị lớn nhất thế giới của các Game thủ máy tính - GameConf! Trong năm nay sự kiện này là sự kiện rất nóng trong giới các game thú, vì vậy nó được tồ chức trong một phòng họp lớn có sức chứa M người, và mỗi đại biểu được dành cho một ghế ngồi. Tất cả các ghế trong phòng họp được sắp xếp theo một hàng ngang để tất cả các đại biếu không có ai bị hạn chế tầm nhìn và tất cã đều có thể nhìn thấy toàn bộ những gì diễn ra trên sân khấu. Các ghế trong phòng họp được đánh số từ 1 đến \(M\), từ trái qua phải.

Hội nghị vừa diễn ra và mới có \(N\) ghế có đại biểu ngồi. Bờm nhận thấy rằng nếu tất cả các đại biểu có mặt ngồi ở các vị trí liên tiếp (chẳng hạn, từ số 5 đến số 10 hay là từ số 8 đến số 1008) thì đại biểu mới đến dễ dàng tìm được chỗ ngồi cho mình: hoặc là bên trái hoặc là bên phải của dãy ghế đã có người ngồi. Trái lại, đại biểu có thể mất nhiều thời gian để lựa chọn chỗ ngồi, và điều đó có thể dẫn đến một loạt các đại biểu phải xếp hàng chờ đợi và khi đó họ có thể rất dễ nổi cáu. Không gì tồi tệ hơn khi xuất hiện các game thủ nổi cáu, nếu không tin bạn có thể sử dụng google search tìm kiếm với từ khóa “game thủ nổi cáu” bạn sẽ tìm thấy rất nhiều bài viết về điều này.

Bờm quyết định xếp lại chỗ ngồi cho các đại biểu sao cho họ ngồi ở các vị trí liên tiếp. Hơn nữa Bờm muốn thực hiện điều này sao cho phải làm phiền (yêu cầu đổi chỗ) ít đại biểu nhất.

Yêu cầu: Hãy giúp Bờm thực hiện công việc đặt ra.

Input

  • Dòng đầu tiên chứa hai số nguyên \(N\) (\(0 < N< 10^5\)) và \(M\) (\(N < M < 10^9\)) - số lượng ghế đã có người ngồi và số lượng ghế có trong hội trường;
  • Dòng thứ hai chứa \(N\) số nguyên dương \(g_1, g_2, ...,g_N\) là chỉ số của các ghế đã có đại biểu ngồi (\(0 < g_i < M, i = 1, 2, ..., N\)).

Output

  • Ghi ra số lượng nhỏ nhất các đại biểu cần di chuyển chỗ để tất cả các đại biểu ngồi ở dãy các vị trí liên tiếp nhau trong hàng ghế.

Example

Test 1

Input
 10
 1 3 10
Output
1
Note

Trong ví dụ chỉ cần di chuyển đại biểu ngồi ở ghế số 10 sang ngồi ở vị trí ghế số 2, khi đó tất cả các đại biểu ngồi ở các vị trí liên tiếp nhau: từ số 1 đến số 3.


Bình luận

Không có bình luận nào.