Diferencija

Ο Mirko ανακάλυψε τι έκανε ο Slavko στην προηγούμενη εργασία και αποφάσισε να ασχοληθεί με κάτι εντελώς αντίθετο από τους πίνακες γραμμάτων: ακολουθίες αριθμών.
Ας ορίσουμε μια τιμή μιας ακολουθίας ως τη διαφορά μεταξύ του μεγαλύτερου και του μικρότερου αριθμού σε αυτήν την ακολουθία. Για παράδειγμα, η τιμή της ακολουθίας ~(3,\;1,\;7,\;2)~ είναι ~6~ και η τιμή της ~(42,\;42)~ είναι 0.
Να βρείτε το άθροισμα των τιμών όλων των υποακολουθιών διαδοχικών στοιχείων μιας δεδομένης ακολουθίας.

Είσοδος

Η πρώτη γραμμή εισόδου περιέχει έναν μόνο ακέραιο αριθμό ~N\;(2 \leq N \leq 300\,000)~, τον αριθμό των στοιχείων της ακολουθίας.
Οι επόμενες ~N~ γραμμές περιέχουν στοιχεία της ακολουθίας. Κάθε στοιχείο είναι ένας θετικός ακέραιος όχι μεγαλύτερος από ~100\,000\,000~.

Έξοδος

Η πρώτη και μοναδική γραμμή εξόδου πρέπει να περιέχει το ζητούμενο άθροισμα.

Παραδείγματα

input

3
1
2
3

output

4

input

4
7
5
7
5

output

12

input

4
3
1
7
2

output

31