Cho dãy số A[] gồm có N phần tử. Ở mỗi thao tác bạn có thể tăng các phần tử trong mảng lên 1 vài đơn vị, hãy xác định số đơn vị tối thiểu cần thêm vào các phần tử trong mảng sao cho mảng trở thành một dãy tăng chặt. Ví dụ dãy 1 2 3 4 9 là một dãy tăng dần.

Input Format

Dòng đầu tiên là số nguyên N. Dòng tiếp theo gồm N số nguyên A[i].(1≤ N ≤ 10^6; 0 ≤ A[i]) ≤ 10^6)

Constraints

.

Output Format

In ra số đơn vị tối thiểu cần thêm vào các phần tử trong mảng để dãy tăng dần.

Ví dụ:

Dữ liệu vào

5
1 2 1 3 2

Dữ liệu ra

6