Mảng không giảm

Nguồn: CSES Problem Set

Đề bài

Cho một mảng gồm $n$ số nguyên $x_1,x_2,\ldots,x_n$.

Bạn muốn biến đổi mảng thành một dãy không giảm, nghĩa là mỗi phần tử phải có giá trị không nhỏ hơn phần tử đứng ngay trước nó:

Trong mỗi thao tác, bạn được chọn một phần tử bất kỳ của mảng và tăng giá trị của phần tử đó lên $1$.

Hãy xác định số thao tác ít nhất cần thực hiện để mảng trở thành một dãy không giảm.

Input

Dòng đầu tiên chứa số nguyên $n$ — số lượng phần tử 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

In ra số thao tác ít nhất cần thực hiện để mảng trở thành một dãy không giảm.

Subtask

• Subtask 1 — 20%: $1 \le n \le 100$; $1 \le x_i \le 100$.
• Subtask 2 — 30%: $1 \le n \le 2000$; $1 \le x_i \le 10^9$.
• Subtask 3 — 50%: $1 \le n \le 2\cdot10^5$; $1 \le x_i \le 10^9$.

Ví dụ

Input

5
3 2 5 1 7

Output

5