Số bước đưa dãy về không giảm (Minimum Increments to Nondecreasing)

Nguồn: Phước Hưng OJ

Phiên bản: Phước Hưng OJ Extended

Đề bài

Cho dãy $n$ số nguyên không âm. Một thao tác được phép tăng một phần tử bất kỳ lên đúng 1. Tìm số thao tác ít nhất để dãy trở thành không giảm, nghĩa là phần tử sau không nhỏ hơn phần tử trước. Không được giảm hay đổi chỗ phần tử.

Input

Dòng đầu chứa $n$ ($1\le n\le100000$). Dòng sau chứa $n$ số nguyên $0\le a_i\le10^9$.

Output

In số phép tăng ít nhất, dùng kết quả số nguyên 64 bit.

Subtask

• Subtask 1 (20%): $n\le5,a_i\le10$.
• Subtask 2 (30%): $n\le500,a_i\le10^4$.
• Subtask 3 (50%): $n\le100000,a_i\le10^9$.

Ví dụ

Ví dụ 1

Input:

5
3 2 5 1 7

Output:

5

Giải thích:

Tăng 2 thành 3 mất 1 lần; tăng 1 thành 5 mất 4 lần; tổng 5.

Ví dụ 2

Input:

4
9 0 0 0

Output:

27

Giải thích:

Ba số 0 phía sau đều phải tăng thành 9, mất 9+9+9 thao tác.