Increasing Array

Nguồn: CSES

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

Đề bài

Cho dãy số nguyên

Một dãy được gọi là không giảm nếu

Trong một thao tác, bạn được chọn đúng một phần tử và tăng nó thêm $1$. Hãy tìm số thao tác nhỏ nhất để biến dãy thành không giảm.

Khi quét từ trái sang phải, nếu giá trị hiện tại nhỏ hơn giá trị đã sửa của phần tử trước, số bước bắt buộc phải cộng chính là hiệu giữa hai giá trị đó.

Input

Dòng đầu chứa $n$. Dòng thứ hai chứa $n$ số nguyên $a_1,\ldots,a_n$.

Output

In số thao tác nhỏ nhất. Kết quả có thể vượt phạm vi int 32-bit.

Subtask

Subtask 1 (20 điểm): $1\le n\le10$, $1\le a_i\le10^3$.

Subtask 2 (30 điểm): $1\le n\le1000$, $1\le a_i\le10^9$.

Subtask 3 (50 điểm): $1\le n\le2\cdot10^5$, $1\le a_i\le10^9$.

Ví dụ

Input

5
3 2 5 1 7

Output

5

Giải thích

Tăng phần tử thứ 2 từ 2 lên 3 cần 1 bước; tăng phần tử thứ 4 từ 1 lên 5 cần 4 bước. Tổng là $1+4=5$.