Increasing Array (Increasing Array)

Nguồn: CSES

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

Đề bài

Cho một dãy $n$ số nguyên dương. Trong một thao tác, bạn được tăng giá trị một phần tử lên đúng 1. Hãy tính số thao tác ít nhất để dãy không giảm, tức $a_i\ge a_{i-1}$ với mọi vị trí sau vị trí đầu. Không được giảm hoặc hoán đổi phần tử.

Input

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

Output

In số thao tác tối thiểu dưới dạng số nguyên 64 bit.

Subtask

• Subtask 1 (20%): $n\le10,a_i\le10$.
• Subtask 2 (30%): $n\le1000,a_i\le10^4$.
• Subtask 3 (50%): $n\le200000,a_i\le10^9$ (miền CSES đầy đủ).

Ví dụ

Ví dụ 1

Input:

5
3 2 5 1 7

Output:

5

Giải thích:

Phải tăng 2→3 (1 lần) và 1→5 (4 lần); tổng 5.

Ví dụ 2

Input:

1
1000000000

Output:

0

Giải thích:

Một phần tử đã là dãy không giảm.