Twice-As-Big Pairs

Difficulty: 2000 4000 ms 128 MB

divide-and-conquer

Count the index pairs i < j with a_i > 2·a_j.

Input: the first line has N; the second line has N integers.

Output: the number of such pairs.

Constraints:

• 1 ≤ N ≤ 10⁵
• |a_i| ≤ 10⁹

Sample Tests

4
5 2 1 3

2

2
1 1

0

Read the Editorial