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.

Scoring

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

Notes

Giải thích cho ví dụ 1:

~f(1,1)=1~, ~f(2,2)=1~, ~f(3,3)=1~, ~f(4,4)=1~: các đoạn độ dài 1 đều có giá trị bằng 1.

~f(1,2)=2~, ~f(2,3)=2~, ~f(3,4)=2~: các đoạn độ dài 2 đều có giá trị bằng 2.

~f(1,3)=2~, đoạn ~[4, 2, 3]~: chỉ có hai phần tử đầu mỗi phía là nhìn thấy.

~f(2,4)=3~, đoạn ~[2, 3, 2]~: cả 3 phần tử đều nhìn thấy.

~f(1,4)=3~, đoạn ~[4, 2, 3, 2]~: phần tử thứ hai không nhìn thấy được từ cả hai phía.

Giải thích cho ví dụ 2:

Trong số 36 đoạn con của dãy, có:

• 8 đoạn giá trị bằng 1

• 14 đoạn giá trị bằng 2

• 11 đoạn giá trị bằng 3

• 3 đoạn giá trị bằng 4