Dãy tăng

Bạn được cho một mảng gồm \(n\) số nguyên dương. Bạn cần biến đổi sao cho mảng này được sắp xếp theo trình tự tăng dần, và mọi phần tử trong mảng đều không nhỏ hơn phần tử đứng trước.

Trong mỗi lần biến đổi, bạn có thể tăng một phần tử lên một đơn vị. Hãy tìm số lần biến đổi ít nhất để thoả mản điều kiện trên.

Input

Dòng đầu tiên chứa hai số nguyên \(n\) \((1 \leq n \leq 2 \times 10^5)\).

Dòng thứ hai chứa \(n\) số nguyên \(a_1, a_2, \ldots, a_n\) \((1 \leq a_i \leq 10^9)\) --- giá trị của mảng \(a\).

Output

• In ra số lần biến đổi ít nhất.

Example

5
3 2 5 1 7

5