Cặp lệch gấp đôi

Bối cảnh và bài toán

Trong một chuỗi đo, một cặp chỉ số (i,j) với i<j được coi là lệch mạnh nếu a[i] > 2*a[j]. Cần đếm số cặp như vậy cho dữ liệu lớn.

Yêu cầu

Đếm số cặp (i,j) thỏa i<j và a[i] > 2*a[j].

Input

• Dòng 1: n.
• Dòng 2: n số nguyên a[i].

Output

In số cặp.

Ràng buộc

• 1 <= n <= 2 * 10^5
• |a[i]| <= 10^9

Chấm điểm

Ví dụ 1

Input

5
1 3 2 3 1

Output

2

Giải thích. Hai cặp hợp lệ là (3 ở vị trí 2, 1 ở vị trí 5) và (3 ở vị trí 4, 1 ở vị trí 5).

Ví dụ 2

Input

5
2 4 3 5 1

Output

3

Giải thích. Các cặp thỏa điều kiện được đếm theo thứ tự chỉ số.

Thông tin bài tập

Nguồn: FULLHOUSE DEV – Self-generated.