Một buổi sáng đẹp trời, J97 ngồi bên cửa sổ, cầm trên tay tách cà phê nóng, ngắm nhìn những đám mây trôi lững lờ. Hôm nay là ngày nghỉ, và J97 muốn dành chút thời gian để suy ngẫm về những gì mình đã trải qua. Giống như nhiều người, cuộc đời J97 là chuỗi những ngày bình thường xen lẫn vài khoảnh khắc đặc biệt, đôi khi ngập tràn niềm vui, đôi khi lại vương chút buồn. Và, như mọi người khác, J97 nhận ra rằng cuộc sống của mình có những "sức nặng" – những lúc thăng trầm rõ rệt hơn, để lại dấu ấn sâu đậm trong tim.

Bất chợt, J97 nghĩ: "Nếu mỗi ngày, mỗi chuỗi ký ức đều là một con số, thì 'sức nặng' của chuỗi ký ức ấy sẽ là gì?"" Cậu hình dung rằng với mỗi đoạn ký ức – từ ngắn nhất chỉ gồm một khoảnh khắc, cho đến dài nhất bao trọn cả năm vừa qua – cậu có thể đo "sức nặng" của đoạn đó: chính là hiệu số giữa khoảnh khắc đẹp nhất và tệ nhất trong chuỗi ký ức. Một ngày thật yên bình sẽ có sức nặng bằng ~0~, còn một tuần với đủ mọi cảm xúc sẽ có sức nặng lớn hơn.

Với ý nghĩ đó, J97 quyết định tìm cách tính tổng tất cả "sức nặng" của những đoạn ký ức trong cuộc đời mình, từ ngắn nhất đến dài nhất. Đây là một bài toán thú vị, và cậu đã tìm ra cách mô phỏng nó bằng một mảng số nguyên ~A~ gồm ~n~ phần tử: ~A_1, A_2, ..., A_n~. Giờ đây, J97 muốn bạn giúp cậu tính tổng sức nặng của tất cả các dãy con liên tiếp của ~A~, để hiểu được sức nặng cuộc đời mình. Sức nặng của một dãy con được định nghĩa là hiệu giữa phần tử lớn nhất và nhỏ nhất trong dãy đó.

Dữ liệu vào:

• Dòng đầu tiên chứa một số nguyên dương ~n~ (~n \leq 4 \times 10^5~).
• Dòng thứ hai chứa ~n~ số nguyên dương ~A_1, A_2, ..., A_n~ (~A_i \leq 10^6~).

Dữ liệu ra:

• Một số nguyên duy nhất biểu thị kết quả.

Ví dụ nhập

3 
1 2 3

Ví dụ xuất

4

Ghi chú

Các sức nặng được tính như sau:

• ~[1, 2] = (2 - 1) = 1~
• ~[1, 3] = (3 - 1) = 2~
• ~[2, 3] = (3 - 2) = 1~

Giới hạn:

• Subtask ~1~ (~30%~ số điểm): ~n \leq 4 \times 10^2~
• Subtask ~2~ (~30%~ số điểm): ~n \leq 10^4~
• Subtask ~3~ (~40%~ số điểm): Không có ràng buộc bổ sung.