Khoảng cách cùng nhóm

Phiên bản: Phước Hưng OJ Extended

Đề bài

Có $N$ học sinh đứng trên một hàng, học sinh thứ $i$ đứng tại vị trí $i$.

Mỗi học sinh thuộc đúng một trong $M$ nhóm. Gọi $A_i$ là chỉ số nhóm của học sinh thứ $i$.

Với hai học sinh ở vị trí $i<j$ và thuộc cùng một nhóm, khoảng cách giữa hai học sinh được xác định là:

Hãy tính tổng khoảng cách của tất cả các cặp học sinh thuộc cùng một nhóm.

Input

Dòng đầu tiên chứa hai số nguyên dương $N$ và $M$, cách nhau bởi một dấu cách.

Dòng thứ hai chứa $N$ số nguyên $A_1,A_2,\ldots,A_N$, cách nhau bởi dấu cách, trong đó $A_i$ là chỉ số nhóm của học sinh thứ $i$.

Output

In ra một số nguyên duy nhất $D$ — tổng khoảng cách của tất cả các cặp học sinh thuộc cùng một nhóm:

Subtask

Trong tất cả các Subtask: $1\le M\le N\le2\cdot10^5$ và $1\le A_i\le M$.

• Subtask 1 — 1,5 điểm: $N\le3000$.
• Subtask 2 — 1,0 điểm: $M=1$.
• Subtask 3 — 1,5 điểm: Không có ràng buộc bổ sung.

Ví dụ

Input

8 3
1 2 1 1 2 3 1 2

Output

31

Giải thích

Nhóm $1$ gồm các học sinh ở vị trí $1,3,4,7$. Tổng khoảng cách giữa các cặp học sinh của nhóm này là:

Nhóm $2$ gồm các học sinh ở vị trí $2,5,8$. Tổng khoảng cách là:

Nhóm $3$ chỉ có một học sinh ở vị trí $6$, nên không tạo ra cặp học sinh nào.

Do đó: