Nghe thêm nhạc trong khi làm bài để tăng phần hấp dẫn: Link nhạc YouTube

Ta cùng biến căn phòng rộng ~0,01m^2~ thành một ngôi nhà khang trang tiện dụng. Little John sống cực kỳ đạm bạc và chăm chỉ xếp gạch thuê trong hai năm, và dành được nửa triệu Biden để mua một căn nhà ở New York. Tuy nhiên, khi chuyển đến, anh đã bị sốc vì nó quá nhỏ. Anh thậm chí còn không thể duỗi ngón tay ra. Bây giờ, hãy tìm cách chúng ta có thể giúp Little John biến nó thành một ngôi nhà tiện dụng. Đầu tiên, chúng ta sẽ xây dựng một khung bền hình tam giác bằng thép vuông mạ kẽm chống gỉ (galvanized square steel) được neo chắc chắn vào tường chứa đầy các thanh thép lưới và bê tông bằng vít giãn nở mượn từ người dì, để ngôi nhà có độ bền đến ~10000~ năm sau cũng chưa hỏng.

Mà trước hết ta cần mua thép vuông mạ kẽm chống gỉ để làm khung đã. Little John té lẹ đến một cửa hàng có bày bán ~n~ thanh thép (vuông mạ kẽm chống gỉ), thanh thép thứ ~i~ có độ dài là ~a_i~.

Bạn cần đếm số lượng cách chọn bộ ba ~(i,j,k)\ (1 \le i < j < k \le n)~ sao cho ba thanh thép đã chọn có độ dài lần lượt là ~a_i, a_j~ và ~a_k~ sẽ tạo thành một khung hình tam giác.

!! Chú ý nhập xuất từ file !!

Input

Nhập vào từ file "TRISTEEL.INP":

• Dòng đầu tiên chứa một số nguyên dương ~n~ ~(1 \le n\le 8000)~ là số lượng thanh thép vuông mạ kẽm chống gỉ.
• Dòng thứ hai chứa ~n~ số nguyên dương ~a_i~ ~(1\le a_i\le 10^5)~ là độ dài của các thanh thép.

Output

In ra file "TRISTEEL.OUT":

• In ra một số nguyên duy nhất là số lượng cách chọn bộ ba ~(i, j, k)~ thỏa mãn điều kiện đề bài.

Subtasks

• Subtask 1: ~40\%~ test có ~n \le 500~;
• Subtask 2: ~30\%~ test có ~n \le 3000~;
• Subtask 3: ~30\%~ test còn lại không có ràng buộc gì thêm.

Sample Input 1

5
1 2 3 4 5

Sample Output 1

3

Giải thích:

• Những bộ ba thỏa mãn đề bài lần lượt là ~(2,3,4), (2,4,5)~ và ~(3,4,5)~.