Kiểm thử tải

Polycarp đang chuẩn bị kiểm thử tải (load testing) cho dịch vụ Fakebook mới. Anh đã thống nhất với bạn bè rằng tại các thời điểm cụ thể, họ sẽ gửi yêu cầu đến hệ thống. Quá trình kéo dài $n$ phút và ở phút thứ $i$, các bạn của anh sẽ gửi $a_i$ yêu cầu.

Polycarp muốn tải hệ thống có dạng tăng nghiêm ngặt đến một thời điểm nào đó rồi giảm nghiêm ngặt ngay sau đó. Cả phần tăng và phần giảm đều có thể trống (tức biến mất). Hai phần tử cạnh nhau bằng nhau là không chấp nhận được.

Polycarp có thể thêm một số lượng yêu cầu bất kỳ vào bất kỳ phút nào (không thể giảm). Hãy tìm tổng số yêu cầu nhỏ nhất mà Polycarp cần thêm để dãy tải thỏa mãn yêu cầu trên.

Dữ liệu vào

• Dòng đầu chứa số nguyên $n$ — số phút kiểm thử.
• Dòng thứ hai chứa $n$ số nguyên $a_1,a_2,\dots ,a_n$.

Dữ liệu ra

In ra một số nguyên duy nhất — tổng số yêu cầu nhỏ nhất cần thêm.

Ràng buộc

• $1\le n\le 100000$
• $1\le a_i\le {10}^9$

Ví dụ