~

Ở nơi Q và C ở có $N$ ngọn núi khác nhau. Mỗi ngọn núi có một độ cao là $a_i$ và các ngọn núi này tạo thành một dãy núi lớn, cao kinh khủng. Để có thể đón được ánh bình minh tuyệt đẹp, Q đã quyết định thức thật sớm và băng qua dãy núi mặc dù việc này rất là mệt mỗi cho một con người lười vận động như C. Nhưng C cũng đâu còn lựa chọn nào khác ngoài việc là cố hết mình và leo cùng cậu ấy @_@

Trong quá trình đi, C tự hỏi liệu mình có đủ sức để băng qua dãy núi không? Cậu tự trả lời câu hỏi này bằng cách tính chênh lệch độ cao của ngọn núi cao nhất và thấp nhất trong quá trình đi và so với thể lực của mình. Nhưng cậu biết một việc còn đáng sợ hơn thế nhiều, đó là cậu không biết C sẽ dừng lại ở ngọn núi nào để ngắm bình minh. Vì vậy, hãy giúp cậu ấy tính tổng độ chênh lệch của ngọn núi cao nhất và thấp nhất trong tất cả dãy núi con và bảo rằng cậu có thể làm được, chayyooo!! Biết rằng một dãy núi con là một dãy các ngọn núi liền kề và không có dãy nào không có núi.

Cảnh tượng mà cả hai đã được ngắm nhìn khi đó, có lẽ họ sẽ không bao giờ có thể quên được. Cảm ơn vì sự giúp đỡ của bạn :>

Input:

• Dòng đầu tiên gồm một số nguyên $N$ số lượng ngọn núi trong dãy núi với $1\le N\le 4\cdot {10}^5.$

• Dòng thứ hai chứa $N$ số nguyên $a_i$ là độ cao các ngọn núi $0\le a_i\le {10}^9.$

Output:

Đáp số của bài toán.

Sample Input

4
0 1 0 6

Sample Output

21

Giải thích

• Dãy {0} có độ chênh lệch là: $0$
• Dãy {1} có độ chênh lệch là: $0$
• Dãy {0} có độ chênh lệch là: $0$
• Dãy {6} có độ chênh lệch là: $0$
• Dãy {0, 1} có độ chênh lệch là: $1$
• Dãy {1, 0} có độ chênh lệch là: $1$
• Dãy {0, 6} có độ chênh lệch là: $6$
• Dãy {0, 1, 0} có độ chênh lệch là: $1$
• Dãy {1, 0, 6} có độ chênh lệch là: $6$
• Dãy {0, 1, 0, 6} có độ chênh lệch là: $6$
• Nên tổng các độ chênh lệch là: $21.$