Trong một trò chơi xây địa hình 2D, một khu vực A gồm ~n~ vùng liên tiếp có độ cao lần lượt là ~A_1, A_2, ..., A_n~.

Khu vực ~A~ được gọi là một ngọn núi khi sườn bên trái của nó tăng đơn điệu và sườn bên phải của nó giảm đơn điệu. Nghĩa là, khi A là ngọn núi với đỉnh núi là vùng có chiều cao ~A_x~, thì ~n~ vùng của ~A~ phải có độ cao đảm bảo ~A_1<A_2<...<A_x~ và ~A_x>...>A_{n-1}>A_n~. (~1 < x < n~). Hai vùng đầu tiên và cuối cùng của khu vực A không được là đỉnh núi.

Yêu cầu

Hãy viết chương trình tính chi phí tối thiểu để đắp khu vực A thành một ngọn núi.

Input

Vào từ file văn bản DAPNUI.INP gồm hai dòng:

• Dòng đầu chứa số nguyên n (~3 \leq n \leq 10^5~)

• Dòng tiếp theo gồm ~n~ số nguyên ~A_1, A_2, ..., A_n~ (~0 \leq A_i \leq 10^9~, ~1 \leq i \leq n~).

Các số trên cùng một dòng cách nhau một khoảng trắng.

Output

Ghi ra file văn bản DAPNUI.OUT một số nguyên duy nhất cho biết chi phí tối thiểu để đắp khu vực A thành một ngọn núi.

Scoring

Sample Input 1

5
1 1 1 1 1

Sample Output 1

4

Sample Input 2

6
3 4 5 6 5 1

Sample Output 2

0