406125: GYM102272 B Đếm Thỏ

Hai thợ săn low_ và lantrungseo đi vào rừng bắt thỏ.

N con thỏ trong rừng đều xếp thành một hàng ngang (theo một cách không hề có sắp xếp trước). Chúng được đánh dấu từ $$$1$$$ đến $$$N$$$ theo thứ tự từ trái qua phải, và ở các vị trí, hai thợ săn đều biết con thỏ ở đó thuộc giống gì. Để cho buổi đi săn thú vị, low_ và lantrungseo đã đưa ra một trò chơi:

- Mỗi người chọn 2 số $$$l$$$ và $$$r$$$ ($$$l \le r$$$) và bắt tất cả các con thỏ trong đoạn đó. Số điểm nhận được của mỗi người chơi sẽ là số lượng giống thỏ khác nhau trong những chú thỏ mà người đó bắt được.

Trong khi low_ chỉ chăm chăm tìm cách để chiến thắng, lantrungseo quan tâm đến việc tính tổng số điểm của tất cả các đoạn có thể chọn. Nói cách khác, lantrungseo quan tâm đến tổng:

$$$$$$\sum_{1 \le l \le r \le N}f(l, r)$$$$$$

Với $$$f(l, r)$$$ là số lượng số giống thỏ khác nhau nằm trên đoạn $$$[l, r]$$$.

Hãy giúp lantrungseo tính ra tổng đó.

Dòng đầu tiên ở mỗi file input chứa $$$T$$$ ($$$1 \le T \le 10$$$) - số bộ test. Mỗi bộ test có format như sau:

- Dòng đầu tiên chứa $$$N$$$ ($$$1 \le N \le 10^6$$$).

- Dòng thứ hai chứa N số: $$$typ_1, typ_2,...,typ_N$$$ ($$$1 \le typ_i \le 10^9$$$) - số thể hiện giống của từng con thỏ. Hai con thỏ $$$i$$$, $$$j$$$, cùng giống khi và chỉ khi $$$typ_i=typ_j$$$.

- Tổng của $$$N$$$ trong tất cả các bộ test không vượt quá $$$2*10^6$$$.

Với mỗi bộ test, in ra trên một dòng duy nhất một số là kết quả bài toán.

40% số điểm ứng với $$$N \le 1000$$$.

2
3
1 2 3
4
1 2 2 3

10
16

Bộ test thứ hai:

$$$f(1, 1)=1$$$, $$$f(1, 2)=2$$$, $$$f(1, 3)=2$$$, $$$f(1, 4)=3$$$, $$$f(2, 2)=1$$$, $$$f(2, 3)=1$$$, $$$f(2, 4)=2$$$, $$$f(3, 3)=1$$$, $$$f(3, 4)=2$$$, $$$f(4, 4)=1$$$.