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.

Ghi chú: bài này với test lớn thì tính toán có thể sẽ ra giá trị vượt ngưỡng Int64, ta cần dùng Python hoặc có cách xử lý khéo léo mới giải quyết được trọn vẹn.