Tam giác cân

Xem PDF
Tất cả bài nộp
Các bài nộp tốt nhất
Xem hướng dẫn
Tác giả:
CaiWinDao
Dạng bài
Điểm: 400 (p) Thời gian: 1.0s Bộ nhớ: 256M Input: bàn phím Output: màn hình

Tam giác cân là tam giác có ít nhất hai cạnh có độ dài bằng nhau. Cho dãy gồm \(N\) số nguyên dương \(a_1\), \(a_2\),..., \(a_N\). Hãy tính số bộ ba chỉ số \((i, j, k)\) với \(1\leq i<j<k\leq N\) sao cho cho ba số \(a_i\), \(a_j\), \(a_k\) là độ dài ba cạnh của một tam giác cân.

Input

  • Dòng đầu ghi số nguyên \(N\) \((3\leq N\leq 5\cdot 10^5)\).
  • Dòng tiếp theo ghi \(N\) số hạng của dãy, mỗi số hạng đều không vượt quá \(10^5\). Các số hạng được ghi cách nhau bởi ít nhất một dấu cách.

Output

  • Ghi ra một số nguyên là số tam giác cân tìm được.

Scoring

  • Subtask \(1\) (\(40\%\) số điểm): \(N\leq 10^3\)
  • Subtask \(2\) (\(30\%\) số điểm): \(N\leq 10^5\)
  • Subtask \(3\) (\(30\%\) số điểm): \(N\leq 5 \cdot 10^5\)

Example

Test 1

Input 
8
5 3 2 9 5 4 9 5
Output 
22

Bình luận