#632. TRICOUNT

Bộ nhớ: 256 MiB Thời gian: 1000 ms Nhập/xuất từ luồng chuẩn
Kiểu bài: Thông thường Kiểu chấm: So sánh văn bản
Đưa lên bởi: Trùm CUỐI

Đề bài

Nguồn: Beginner Free Contest 7

Cho N thanh sắt, thanh sắt thứ i có độ dài là A_i . Đếm số lượng bộ ba (i,j,k)\ (1 ≤ i < j < k ≤ N) sao cho ba thanh sắt độ dài lần lượt là A_i, A_j A_k tạo thành một tam giác.

Dữ liệu vào:

  • Dòng đầu tiên chứa số nguyên dương N tương ứng với số lượng thanh sắt;
  • Dòng thứ hai chứa N số nguyên, số thứ i có giá trị là A_i tương ứng với độ dài thanh sắt thứ i .

Dữ liệu ra:

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

Ví dụ:

Dữ liệu vào:
5
1 2 3 4 5

Dữ liệu ra:

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) .

Giới hạn:

Trong tất cả các test, 0 ≤ A_i ≤ 1000 .

  • Subtask \#1\ (20\%): 1 ≤ N ≤ 500 ;
  • Subtask \#2\ (40\%): 1 ≤ N ≤ 3000 ;
  • Subtask \#3\ (40\%): 1 ≤ N ≤ 8000 .