Hằng đẳng thức đáng nhớ đã quá quen thuộc rồi. Hãy để sư phụ ami giới thiệu cho các bạn hằng đẳng thức đáng quên.

ami có một dãy số \(a\) gồm \(n\) phần tử \(a_1\), \(a_2\), ..., \(a_n\). Hẳng đẳng thức đáng quên của dãy số trên được tính bằng công thức sau:

\(A = \sum |i - j|\), với tất cả các cặp \(i \leq j\) và \(a_i\) = \(a_j\).

Nói cách khác, \(A\) là tổng khoảng cách các vị trí \((i, j)\) mà \(a_i = a_j\).

Các bạn cần tính hằng đẳng thức này như một bài tập về nhà.

Input

• Dòng đầu tiên chứa một số nguyên dương \(n\) là số phần tử trong mảng \(a\).

• Dòng tiếp theo chứa \(n\) số nguyên dương \(a_i\) là một phần tử của mảng \(a\).

Output

• Hãy in ra kết quả của hằng đẳng thức đáng quên.

Scoring

• Trong tất cả các test, \(1 \leq a_i \leq n\).

• Subtask \(1\) (\(25\%\) số điểm): \(1 \leq n \leq 100\).

• Subtask \(2\) (\(25\%\) số điểm): \(1 \leq n \leq 1000\).

• Subtask \(3\) (\(50\%\) số điểm): \(1 \leq n \leq 10^5\).

Example

3
 2 3 1

0

4
 2 1 2 1

4