Số thao tác giúp mảng tăng dần 1.

Bối cảnh

Bài toán được mô tả qua yêu cầu và dữ liệu dưới đây.

Yêu cầu

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 dần. Ví dụ dãy 1 2 3 4 5 là một dãy tăng dần.Còn dãy 1 2 3 4 4 không phải tăng dần.

Input

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)

Output

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.

Ràng buộc

Đề gốc không nêu ràng buộc riêng.

Ví dụ 1

Input

5
1 2 1 3 2

Output

6

Thông tin học tập

• Buổi: B09
• Concepts: 1D arrays, input, traversal, aggregation
• Giới hạn kiến thức: B01-B09
• Time limit: 2 seconds
• Memory limit: 20 MB
• Point: 10