Krov

Σας δίνεται ένα ιστόγραμμα που αποτελείται από ~N~ στήλες υψών ~X_1, X_2, ... , X_N,~ αντίστοιχα. Το ιστόγραμμα πρέπει να μετατραπεί σε στέγη χρησιμοποιώντας μια σειρά λειτουργιών. Μια στέγη είναι ένα ιστόγραμμα που έχει τις ακόλουθες ιδιότητες:
● Μια μονή στήλη ονομάζεται κορυφή της οροφής. Έστω η στήλη στη θέση i.
● Το ύψος της στήλης στη θέση ~j~ ~(1 \le j \le N)~ είναι \(h_j​ = ​h_i-|i-j|\).
● Όλα τα ύψη ​~h_j~ είναι θετικοί ακέραιοι.

Μια πράξη μπορεί να αυξάνει ή να μειώνει τα ύψη μιας στήλης του ιστογράμματος κατά 1. Είναι καθήκον σας να προσδιορίσετε τον ελάχιστο αριθμό εργασιών που απαιτούνται για να μετατρέψετε το δεδομένο ιστόγραμμα σε στέγη.

Είσοδος

Η πρώτη γραμμή εισαγωγής περιέχει τον αριθμό ~N~ ~(1 \le N \le 10^5)~, τον αριθμό των στηλών στο ιστόγραμμα. Η ακόλουθη γραμμή περιέχει ​~N~ αριθμούς ~X_i~ ~(1 \le X_i \le 10^9)~, τα αρχικά ύψη στηλών.

Έξοδος

Πρέπει να εξάγετε τον ελάχιστο αριθμό λειτουργιών από την εργασία.

Βαθμολογία

Σε περιπτώσεις δοκιμών αξίας 60% των συνολικών πόντων, θα ισχύει \(N​\le 5\,000\).

Παραδείγματα

input

4
1 1 2 3

output

3

Επεξήγηση του 1ου παραδείγματος:

Αυξάνοντας το ύψος της δεύτερης, τρίτης και τέταρτης στήλης, δημιουργήσαμε μια στέγη όπου η τέταρτη στήλη είναι η κορυφή της οροφής.

input

5
4 5 7 2 2

output

4

Επεξήγηση του 2ου παραδείγματος:

Μειώνοντας το ύψος της τρίτης στήλης τρεις φορές και αυξάνοντας το ύψος της τέταρτης στήλης, μετατρέψαμε το ιστόγραμμα σε στέγη. Το παράδειγμα απεικονίζεται παρακάτω.

input

6
4 5 6 5 4 3

output

0