Bạn được cho một mảng \(x_1,x_2,\dots,x_n\). Gọi \(d(a,b)\) là số giá trị phân biệt trong mảng con \(x_a,x_{a+1},\dots,x_b\).

Nhiệm vụ của bạn là tính tổng \(\sum_{a=1}^n \sum_{b=a}^n d(a,b)\), tức là tổng của \(d(a,b)\) trên tất cả các mảng con.

Input

Dòng đầu tiên chứa một số nguyên \(n\): kích thước mảng.

Dòng tiếp theo chứa \(n\) số nguyên \(x_1,x_2,\dots,x_n\): các phần tử của mảng.

Output

In ra một số nguyên: tổng cần tìm.

Constraints

• \(1 \le n \le 2 \cdot 10^5\)

• \(1 \le x_i \le 10^9\)

Example

5
1 2 3 1 1

29

Explanation

Trong mảng này, có \(6\) mảng con có \(1\) giá trị phân biệt, \(4\) mảng con có \(2\) giá trị phân biệt và \(5\) mảng con có \(3\) giá trị phân biệt. Do đó, tổng là \(6\cdot1+4\cdot2+5\cdot3=29\).