HSG lớp 9 Thành phố Vinh - Bài 4 - Phần thưởng

Point: 100.0

Time limit: 1.0s

Memory limit: 250 M

Input: BONUS.INP

Output: BONUS.OUT

Author:

Pham Anh Tu

Problem types

Ngôn ngữ cho phép

C, C#, C++, Java, Pascal, Python, Text

Trong phần chơi thi đấu GARA STEM của ngày hội Stem cấp thành, phần thưởng cho đội thắng cuộc là tổng trọng số của tất cả các dãy con liên tiếp trong dãy số \(A\) cho trước.

Định nghĩa trọng số của một dãy số nguyên là chênh lệch giữa phần tử lớn nhất và phần tử nhỏ nhất trong dãy.

Yêu cầu

Cho dãy số nguyên dương \(A = (a_1,a_2,...,a_n)\). Hãy tìm phần thưởng cho đội thắng cuộc.

Input

Dòng đầu chứa một số nguyên dương \(n\).
Dòng 2 chứa \(n\) số nguyên dương \(a_1,a_2,\ldots,a_n\).

Output

Ghi ra một số nguyên duy nhất là kết quả tìm được.

Constraints

\(1\le n\le 10^6\)
\(1\le a_i\le 10^6\)

Example

Input	Output	Explain
3 1 2 3	4	Dãy rỗng và các dãy có 1 phần tử \((1),(2),(3)\) đều có trọng số \(0\) Dãy \((1,2),(2,3)\) đều có trọng số \(1\) Dãy \((1,2,3)\) có trọng số \(2\)
4 3 1 7 2	31