THỰC HÀNH

(Đề đề xuất DHBB 2017 của THPT CHUYÊN VĨNH PHÚC)

Cô giáo dạy toán rất không ưa Steve và thường gọi Steve lên bảng giải những bài rất khó. Hôm nay cô giáo viết lên bảng dãy số nguyên không âm a₁, a₂, …, a_n và yêu cầu dùng ít phép biến đổi nhất để đưa về dãy số mới sao cho trong đó có h số liên tiếp nhau tạo thành một dãy tăng dần từ 1 đến h, tức là tồn tại i sao cho a_i = 1, a_(i+1) = 2, …, a_(i+h-1) = h. Nội dung mỗi phép biến đổi là tăng một số tùy chọn trong dãy lên một đơn vị.

Dĩ nhiên, anh bạn tội nghiệp Steve của chúng ta lại bị gọi lên bảng.

Yêu cầu: Hãy xác định số phép biến đổi tối thiểu Steve cần thực hiện hoặc đưa ra số -1 nếu không tồn tại cách nhận được dãy số mới theo yêu cầu.

Dữ liệu vào:

• Dòng đầu tiên chứa hai số nguyên dương n và h được ghi cách nhau một dấu cách.
• Dòng thứ hai chứa n số nguyên dương a₁, a₂, …, a_n, hai số liên tiếp được ghi cách nhau một dấu cách.

Dữ liệu ra:

            Môt số nguyên là đáp số của bài toán.

Ví dụ:

Dữ liệu vào:
4 3
1 1 0 2

Dữ liệu ra:
3

Giải thích: Tắng a₃ lên 2 lần từ 0 lên 2, tăng a₄ lên 1 lần từ 2 lên 3. Mất 3 phép biến đổi.

Giới hạn: 2 ≤ n ≤ 2.10⁵; 1 ≤ h ≤ n; 1 ≤ a_i ≤ n.