Tổng Các Giá Trị Nhỏ Nhất

Cho một hoán vị $A$ gồm $n$ số nguyên từ $1$ đến $n$.

Với mỗi đoạn liên tiếp không rỗng $A_l,\dots ,A_r$, lấy giá trị nhỏ nhất xuất hiện trong đoạn đó. Hãy tính tổng của các giá trị nhỏ nhất trên tất cả $n(n+1)/2$ đoạn:

$\sum \min (A_l,A_{l+1},\dots ,A_r)$, với $1\le l\le r\le n$.

Input

• Dòng đầu chứa số nguyên $n$.
• Dòng thứ hai chứa hoán vị $A_1,A_2,\dots ,A_n$.

Output

• In một số nguyên là tổng cần tìm.

Constraints

• $1\le n\le 2\cdot 10^5$.
• $A$ là một hoán vị của $1,\dots ,n$.
• Kết quả có thể vượt quá phạm vi số nguyên $32$ bit.

Scoring

• Subtask $1$ ($50\%$ số điểm): $n\le 200$.
• Subtask $2$ ($50\%$ số điểm): Không có giới hạn bổ sung.

Example

5
3 1 5 2 4

28