Độ chênh lệch

Leo núi là một hoạt động giúp tăng cường thể lực và cải thiện tinh thần, thể chất rất tốt cho con người. Nó là sự kết hợp khéo léo giữa chân và tay để đứng vững ở những nơi có địa hình hiểm trở, sức bền để di chuyển trên một quãng đường dài đồng thời kết hợp với hoạt động của mắt để quan sát các vật cản ở phía trước. Ngoài ra nó còn giúp tăng cường tuần hoàn, giảm mỡ máu, giảm thiểu nguy cơ các bệnh tim mạch, thần kinh. Sau thời gian học tập và nghiên cứu vất vả, nhận thấy leo núi là hoạt động phù hợp để cải thiện sức khỏe của mình, Sơn quyết định đến Hà Giang để thử sức với môn thể thao này.

Nơi Sơn đến có $n$ ngọn núi, ngọn núi thứ $i$ có độ cao $h_i$. Mỗi ngày, Sơn sẽ chọn một dãy các ngọn núi liên tiếp từ $l$ đến $r$ ($1\le l\le r\le n$) để đi qua. Độ chênh lệch của một dãy các ngọn núi được tính bằng độ cao của ngọn núi cao nhất trừ đi độ cao của ngọn núi thấp nhất (dãy chỉ gồm một ngọn núi có độ chênh lệch bằng $0$). Độ chênh lệch của các ngọn núi càng lớn thì số lượng calories tiêu thụ càng nhiều.

Yêu cầu: Sơn có thắc mắc là tổng độ chênh lệch của mọi dãy các ngọn núi ở nơi cậu đến là bao nhiêu để ước tính xem mình được lợi ích gì sau khi leo núi. Hãy giúp Sơn nhé.

Dữ liệu vào

• Dòng đầu tiên chứa số nguyên $n$ là số ngọn núi nơi quê nhà của Sơn $(1\le n\le 4·{10}^5)$.
• Dòng thứ hai chứa $n$ số nguyên $h_1,h_2,\dots ,h_n$ là độ cao của các ngọn núi $(0\le h_i\le {10}^7)$.

Dữ liệu ra

Một số nguyên duy nhất là tổng độ chênh lệch của mọi dãy các ngọn núi.

Ràng buộc

• $1\le n\le 4·{10}^5$.
• $0\le h_i\le {10}^7$.

Subtasks

• Subtask 1 ($20\%$ số điểm): $n\le 100$.
• Subtask 2 ($30\%$ số điểm): $n\le 5000$.
• Subtask 3 ($50\%$ số điểm): không có ràng buộc gì thêm.

Ví dụ