Vậy là Đại hội võ lâm đã bế mạc, các võ sĩ lại chia tay nhau mỗi người một ngả. Dế Mèn và Dế Trũi mỗi người một ngựa tung tăng về quê nhà.

Đường về quê của hai võ sĩ phải đi qua lần lượt ~n~ ngôi làng được đánh số từ ~1~ đến ~n~. Hiện tại, họ đang ở làng ~1~, quê nhà của họ là làng thứ ~n~. Để có thêm lộ phí, hai võ sĩ cần lập kế hoạch mua, bán cỏ tại các ngôi làng trên đường họ trở về. Tại ngôi làng thứ ~i~ giá mua vào, bán ra một bao cỏ là ~a_i~ đồng. Biết rằng, mỗi ngựa tại một thời điểm chỉ thồ được nhiều nhất một bao cỏ và tại mỗi ngôi làng chỉ được phép mua hoặc bán nhiều nhất một bao cỏ.

Yêu cầu: Tính số tiền lãi nhiều nhất mà hai võ sĩ Dế Mèn và Dế Trũi có thể kiếm được nhờ việc mua, bán cỏ trên hành trình trở về quê nhà.

Input

• Dòng đầu tiên chứa một số nguyên dương ~n~ ~(1 \le n \le 10^6)~;

• Dòng thứ hai chứa ~n~ số nguyên dương ~a_1, a_2, \dots, a_n~, ~a_i \le 10^9~ với ~1 \le i \le n~;

Output

Một số nguyên duy nhất là số tiền lãi lớn nhất mà hai võ sĩ có thể kiếm được nhờ việc buôn cỏ.

Scoring

Sample Input 1

7
1 2 9 4 3 7 8

Sample Output 1

18

Notes

• Tại làng ~1~: Dế Mèn mua cỏ.

• Tại làng ~2~: Dế Trũi mua cỏ.

• Tại làng ~3~: Dế Mèn bán cỏ (lãi ~8~ đồng).

• Tại làng ~4~: Không mua bán gì.

• Tại làng ~5~: Dế Mèn mua cỏ.

• Tại làng ~6~: Dế Trũi bán cỏ (lãi ~5~ đồng).

• Tại làng ~7~: Dế Mèn bán cỏ (lãi ~5~ đồng).