Mảng tăng dần

Trong một phiên tòa đặc biệt, FullHouse Dev được giao nhiệm vụ giải quyết một vụ án liên quan đến một mảng số nguyên. Để chứng minh sự vô tội của thân chủ, họ cần phải biến đổi mảng này thành một mảng tăng dần với số lần thao tác ít nhất. Với tinh thần công lý và kỹ năng lập trình xuất sắc, FullHouse Dev bắt đầu phân tích và giải quyết vấn đề này.

Bài toán

FullHouse Dev được cung cấp một mảng gồm \(n\) số nguyên. Họ cần phải biến đổi mảng sao cho nó trở thành mảng tăng dần, nghĩa là mỗi phần tử phải lớn hơn hoặc bằng phần tử đứng trước nó. Trong mỗi bước, họ có thể tăng giá trị của bất kỳ phần tử nào lên 1. Nhiệm vụ của họ là tìm ra số bước tối thiểu cần thực hiện.

INPUT FORMAT:

• Dòng đầu tiên chứa một số nguyên \(n\): kích thước của mảng.
• Dòng thứ hai chứa \(n\) số nguyên \(x_1, x_2, \ldots, x_n\): các phần tử của mảng.

OUTPUT FORMAT:

• In ra số bước tối thiểu cần thực hiện.

Ràng buộc:

• \(1 \leq n \leq 2 \cdot 10^5\)
• \(1 \leq x_i \leq 10^9\)

Ví dụ

INPUT

5
3 2 5 1 7

OUTPUT

5

Giải thích

Để biến đổi mảng thành mảng tăng dần, FullHouse Dev cần thực hiện các bước sau:

1. Tăng phần tử thứ 2 từ 2 lên 3.
2. Tăng phần tử thứ 4 từ 1 lên 5.
3. Tăng phần tử thứ 4 từ 5 lên 6.
4. Tăng phần tử thứ 4 từ 6 lên 7.
5. Tăng phần tử thứ 4 từ 7 lên 8.

Sau 5 bước, mảng trở thành [3, 3, 5, 8, 7], thỏa mãn yêu cầu tăng dần. Đây là số bước tối thiểu cần thực hiện.