Trên đường đi học về, trông thấy tuankiet65 đang lúi húi cắt các miếng gỗ. Sau khi nghe kể đầu đuôi, winkhanh cười bảo:

“Cậu là người có chí lớn đấy, tôi muốn đưa hình ảnh của đất nước chúng ta vươn tầm châu lục, tôi có một kế hoạch, cậu muốn làm chứ?"

“Kế hoạch gì cơ?”

“Chúng ta sẽ xây dựng một rừng cây độc đáo nhất thế giới“

Rừng cây winkhanh muốn xây dựng sẽ là một khu rừng trồng tất cả các loại cây đặc trưng của Việt Nam. Tuy nhiên như thế vẫn chưa đủ, anh ta còn muốn chiều cao của các cây trong rừng phải tăng giảm xen kẽ giống đường zigzag. Giả sử chiều cao của các cây trong rừng là h[i] với (i = 1, 2, 3, … n), thì h[1] < h[2] > h[3] < h[4]... hoặc h[1] > h[2] < h[3] > h[4]...

Hiện nay, winkhanh đã trồng được 1 khu rừng với rất nhiều loại cây, tuy nhiên chiều cao của cây vẫn chưa thật sự ưng ý. Anh muốn thay đổi chiều cao các cây sao cho chiều cao của chúng thỏa mãn điều kiện của khu rừng zigzag bằng cách thuê người cắt bớt chiều cao các cây sao cho khu rừng trở thành khu rừng zigzag. Dĩ nhiên không thể cắt cho chiều cao của cây giảm xuống 0, vì như vậy cây sẽ chết.

“Nhưng bạn ơi, thuê người tốn tiền lắm, chúng ta làm gì có tiền” - tuankiet65 chán nản

Vì cắt càng nhiều thì càng tốn tiền, đã đến lúc các bạn học sinh chuyên tin THCS ra tay. Hãy giúp đỡ winkhanh và tuankiet65 tiết kiệm tiền bằng cách tính ra tổng chiều cao phải cắt ít nhất sao cho rừng cây trở thành rừng ziczac.

Yêu cầu: Cho độ dài hiện tại của các cây trong khu rừng là h[i] với i = 1, 2, 3,..., N với N là tổng số cây. Hãy tính tổng chiều cao cây phải cắt ít nhất.

Input:

• Dòng đầu gồm số nguyên N là tổng số cây (N <= 10⁶)

• Dòng thứ 2 gồm N số nguyên dương h[i] là chiều cao của cây thứ i. (h[i] <= 10⁹)

Output: Gồm 1 dòng duy nhất ghi một số nguyên là tổng độ dài cây cần cắt. Ghi -1 nếu không tìm được bất kì phương án nào.