Cho dãy số nguyên dương ~a_1, a_2, \dots, a_N~. Với mỗi đoạn con ~[l, r]~ ~(1 \le l \le r \le N)~:

• Một phần tử ~a_i~ ~(l \le i \le r)~ được gọi là nhìn thấy từ bên trái, nếu không tồn tại phần tử ~a_j~ ~(l \le j < i)~ sao cho ~a_j \ge a_i~.
• Một phần tử ~a_i~ ~(l \le i \le r)~ được gọi là nhìn thấy từ bên phải, nếu không tồn tại phần tử ~a_j~ ~(i < j \le r)~ sao cho ~a_j \ge a_i~. Giá trị của đoạn ~[l, r]~, ký hiệu ~f(l, r)~, là số lượng chỉ số ~i~ ~(l \le i \le r)~ khác nhau được nhìn thấy từ ít nhất một trong hai phía.

Yêu cầu: Tính tổng giá trị của tất cả các đoạn con ~[l, r]~, nghĩa là tính tổng ~\sum_{l=1}^{N} \left( \sum_{r=l}^{N} f(l,r) \right)~.

Input

• Dòng 1: số nguyên ~N~ ~(1 \le N \le 100000)~.
• Dòng 2: ~N~ số nguyên ~a_1, a_2, \dots, a_N~ ~(1 \le a_i \le 10^9)~.

Output

In ra một số nguyên - tổng giá trị của tất cả các đoạn con.

Sample Input 1

4
4 2 3 2

Sample Output 1

18

Sample Input 2

8
7 2 3 2 4 3 3 7

Sample Output 2

81