Cho tập hợp ~A~ gồm ~n~ phần tử phân biệt. Đếm số tập con có ~2~ phần tử của ~A~.

Input

Dòng đầu tiên gồm số nguyên dương ~n~ với ~1 \le n \le 10^5~, dòng tiếp theo gồm ~n~ phần tử có giá trị tuyệt đối không vượt quá ~10^6.~

Output

Số tập con cần tìm.

Sample input

4
3 5 7 9

Output

6

Ghi chú: sau khi giải bài này xong thì bạn có thấy thông tin nào không cần thiết hay không? ^^

Thầy Luna cho đề kiểm tra cho ~n~ SV làm và sau khi chấm thì phát hiện ra nhiều bài bằng điểm nhau. Thực ra đó là chuyện bình thường nhưng thầy lại khá nhạy cảm nên muốn gọi tất cả các cặp SV bằng điểm nhau lên vấn đáp lại xem có copy bài của nhau hay không. Hỏi thầy phải hỏi tất cả bao nhiêu cặp?

Input

Dòng đầu tiên gồm số SV là ~n~, trong đó ~2 \le n \le 10^5.~ Dòng tiếp theo gồm điểm số của các SV, các số này là số tự nhiên có giá trị không quá ~10^6.~

Output

Số cặp SV thầy cần vấn đáp.

Sample input 1

5
1 1 1 2 2

Sample output

4

Giải thích: nếu đánh số các SV là ~1,2,3,4,5~ thì các cặp bị vấn đáp sẽ là: ~(1,2),(2,3),(3,1)~ và ~(4,5).~

Trên mặt phẳng tọa độ Oxy cho ~n~ điểm được đánh số ~1,2,...,n~ có tọa độ dạng ~(x,y),~ các điểm có thể bị trùng nhau. Đếm số cặp điểm ~A,B~ có tọa độ phân biệt sao cho trung trực của đoạn ~AB~ thì không đi qua gốc tọa độ ~O~.

Input

Dòng đầu tiên gồm số lượng điểm là ~n~, trong đó ~2 \le n \le 10^5.~ Dòng thứ hai gồm hoành độ của các điểm và dòng thứ ba là tung độ của các điểm; các số này có giá trị tuyệt đối không quá ~10^3~ (các điểm có thể bị lặp lại).

Output

Số cặp điểm cần tìm.

Sample input 1

4
1 2 2 2
2 1 1 5

Sample output

3

Giải thích: STT các cặp điểm thỏa mãn là ~(1,4),(2,4),(3,4)~.

Thầy Tina có ~n~ đoạn thẳng đánh số từ ~1,2,...,n~ có độ dài là các số nguyên dương không nhất thiết phân biệt. Thầy muốn chọn ra bốn đoạn thẳng trong số đó sao cho tạo được một hình bình hành. Hỏi thầy Tina có bao nhiêu cách?

Input

Dòng đầu tiên gồm số nguyên dương ~n~ với ~4 \le n \le 10^5.~ Dòng tiếp theo gồm ~n~ số nguyên dương không vượt quá ~10^6.~

Output

Số cách chọn cần tìm.

Sample input

6
1 1 1 1 2 2

Sample output

7

Giải thích: hình bình hành thì có các cặp cạnh đối bằng nhau, vì thế ta cần chọn ra hai cặp số bằng nhau (nếu cả bốn số bằng nhau luôn cũng được). Như thế ta có thể chọn bốn đoạn độ dài ~1~ với ~1~ cách hoặc chọn ~2~ đoạn độ dài ~1~ đi cùng với ~2~ đoạn độ dài ~2~, có ~6~ cách, tổng cộng là ~1+6=7~ cách.

Thầy Luna cho ~n~ SV thi thử để khảo sát việc lập đội tuyển ICPC, điểm số của mỗi SV là một số tự nhiên. Thầy xét tất cả các cách có thể để tạo thành một bộ ba SV và ứng với mỗi cách, thầy tính tổng điểm của ~3~ bạn. Hãy giúp thầy trả lời các câu hỏi sau đây: tổng điểm lớn nhất, tổng điểm nhỏ nhất và tổng điểm trung bình của các team là bao nhiêu (làm tròn xuống)?

Input

Dòng đầu tiên gồm số nguyên dương ~n~ với ~3 \le n \le 10^5~, dòng tiếp theo gồm điểm số của các SV có giá trị không quá ~10^6.~

Output

Câu trả lời cho ba câu hỏi ở trên.

Sample input

4
5 5 6 7

Sample output

18 16 17

Giải thích: rõ ràng có ~4~ cách lập đội tuyển là chọn SV có số thứ tự ~(1,2,3),(2,3,4),(3,4,1),(4,1,2)~ với tổng điểm của tất cả các cách là ~(5+5+6)+(5+6+7)+(6+7+5)+(7+5+5)=69.~

Vì thế điểm trung bình sẽ là ~69/4=17.25~, làm tròn thành ~17.~ Điểm max = ~5+6+7=18~ và điểm min = ~5+5+6=16.~

Các đại pháp sư Trung Hoa trong CLB H3.2 đã sáng tạo ra một bảng hình chữ nhật ma thuật có kích thước ~n \times m~ (gồm ~n~ dòng và ~m~ cột), trên đó được điền các số nguyên dương. Những em SV K19, những thành viên mới của CLB muốn nhận được bí kíp của các đại pháp sư này thì phải chọn ra được bốn ô trong bảng thỏa mãn đồng thời các điều kiện sau:

• Bốn ô đó là đỉnh của hình chữ nhật có cạnh song song hoặc vuông góc với cạnh của bảng ban đầu.
• Trên bốn số điền trên bốn ô đó, có ít nhất ~75 \%~ là số chính phương.
• Người đi sau sẽ không được chọn trùng lại cả bốn ô của người đi trước.

Hỏi có tất cả bao nhiêu thành viên sẽ có thể nhận được bí kíp của các đại pháp sư?

Input

Dòng đầu tiên gồm số nguyên dương ~n, m~ với ~2 \le n, m \le 500.~ Trong các dòng tiếp theo là mô tả thông tin của bảng, mỗi số trên bảng là nguyên dương và không vượt quá ~10^9.~

Output

Số em SV may mắn.

Sample input

3 3
1 2 9
4 5 6
1 8 4

Sample output

3

Giải thích: có ba hình chữ nhật thỏa mãn với số trên các đỉnh là: ~(1,9,4,6)~, ~(4,6,1,4)~ và ~(1,9,1,4).~

Cho tập hợp ~A~ gồm ~n~ phần tử không nhất thiết phân biệt, còn gọi là đa tập hay multiset. Đếm số tập con có 2 phần tử của ~A~.

Input

Dòng đầu tiên gồm số nguyên dương ~n~ với ~1 \le n \le 10^5,~ dòng tiếp theo gồm ~n~ phần tử có giá trị tuyệt đối không vượt quá ~10^6~, các số có thể bị lặp lại.

Output

Số tập con cần tìm.

Sample input

4
1 1 2 2

Output

3

Giải thích

Các tập con cần tìm là: ~(1,1)~, ~(2,2)~ và ~(1,2)~. Chú ý rằng có nhiều cách để tạo được tập ~(1,2)~ nhưng ta chỉ đếm một lần thôi.

Ghi chú: bạn có thấy được điểm khó của bài này so với phiên bản dễ hay không? Nếu đề bài hỏi số tập con có ~3~ phần tử thì bạn có làm được không? ^^