Tìm Con Số May Mắn Của Peter

Cũng như bao người, Tết 2025 này Peter cũng đi chùa rút quẻ. Nhưng thay vì nhận được lời khuyên, anh lại nhận được một con số may mắn. Nếu có con số này, cả năm Peter sẽ gặt hái được rất nhiều tiền.

Tuy nhiên, quẻ bói không cho anh trực tiếp con số may mắn, mà lại đưa ra một dãy số gồm n số:
$$ a_1, a_2, a_3, ..., a_n $$

Số may mắn chính là số lượng các số x thỏa mãn điều kiện:

• x và hai số bất kỳ trong dãy số a có thể tạo thành một tam giác không suy biến.

Peter không biết cách tìm ra con số may mắn này, hãy giúp anh ấy nhé!

Dữ liệu vào

• Dòng đầu tiên chứa số nguyên n $(2 ≤ n ≤ 5 * 10^6).
• Dòng thứ hai chứa n số nguyên a₁, a₂, ..., aₙ (1 ≤ a_i ≤ 10^9).

Dữ liệu ra

• Xuất ra một số nguyên duy nhất: số lượng số x tìm được.

Ví dụ

Input

5
9 5 6 7 9

Output

6

*Tam giác không suy biến là một tam giác có ba cạnh thỏa mãn Định lý bất đẳng thức tam giác. Cụ thể, đối với ba cạnh của tam giác, nếu ba cạnh có độ dài là a, b, và c, thì để chúng có thể tạo thành một tam giác không suy biến, cần phải thỏa mãn các điều kiện sau:

• a + b > c
• a + c > b
• b + c > a

Giới hạn

• Subtask 1: 30% testcase (n ≤ 100)
• Subtask 2: 30% testcase (n ≤ 1000)
• Subtask 3: 40% testcase không giới hạn gì thêm