A Tale of Two Lands
Contest: Codeforces Round 561 (Div. 2)
Difficulty rating: 1500
Tags: binary search, sortings, two pointers

The legend of the foundation of Vectorland talks of two integers $$$x$$$ and $$$y$$$. Centuries ago, the array king placed two markers at points $$$|x|$$$ and $$$|y|$$$ on the number line and conquered all the land in between (including the endpoints), which he declared to be Arrayland. Many years later, the vector king placed markers at points $$$|x - y|$$$ and $$$|x + y|$$$ and conquered all the land in between (including the endpoints), which he declared to be Vectorland. He did so in such a way that the land of Arrayland was completely inside (including the endpoints) the land of Vectorland.

Here $$$|z|$$$ denotes the absolute value of $$$z$$$.

Now, Jose is stuck on a question of his history exam: "What are the values of $$$x$$$ and $$$y$$$?" Jose doesn't know the answer, but he believes he has narrowed the possible answers down to $$$n$$$ integers $$$a_1, a_2, \dots, a_n$$$. Now, he wants to know the number of unordered pairs formed by two different elements from these $$$n$$$ integers such that the legend could be true if $$$x$$$ and $$$y$$$ were equal to these two values. Note that it is possible that Jose is wrong, and that no pairs could possibly make the legend true.

Input format:
The first line contains a single integer $$$n$$$ ($$$2 \le n \le 2 \cdot 10^5$$$)  — the number of choices.

The second line contains $$$n$$$ pairwise distinct integers $$$a_1, a_2, \dots, a_n$$$ ($$$-10^9 \le a_i \le 10^9$$$) — the choices Jose is considering.

Output format:
Print a single integer number — the number of unordered pairs $$$\{x, y\}$$$ formed by different numbers from Jose's choices that could make the legend true.

Constraints:
Time limit: 1.0 s
Memory limit: 256.0 MB

Note:
Consider the first sample. For the pair $$$\{2, 5\}$$$, the situation looks as follows, with the Arrayland markers at $$$|2| = 2$$$ and $$$|5| = 5$$$, while the Vectorland markers are located at $$$|2 - 5| = 3$$$ and $$$|2 + 5| = 7$$$:

The legend is not true in this case, because the interval $$$[2, 3]$$$ is not conquered by Vectorland. For the pair $$$\{5, -3\}$$$ the situation looks as follows, with Arrayland consisting of the interval $$$[3, 5]$$$ and Vectorland consisting of the interval $$$[2, 8]$$$:

As Vectorland completely contains Arrayland, the legend is true. It can also be shown that the legend is true for the pair $$$\{2, -3\}$$$, for a total of two pairs.

In the second sample, the only pair is $$$\{3, 6\}$$$, and the situation looks as follows:

Note that even though Arrayland and Vectorland share $$$3$$$ as endpoint, we still consider Arrayland to be completely inside of Vectorland.

Example input:
3
2 5 -3

Example output:
2

Example input:
2
3 6

Example output:
1

Editorial:
Formally, the condition for the legend being true reads
$$$$$$\min(\vert x - y \vert, \vert x + y \vert) \le \vert x \vert, \vert y \vert \le \max(\vert x - y \vert, \vert x + y \vert)$$$$$$
Now, it is possible to characterize when this condition happens through casework on the signs and sizes of $$$x$$$ and $$$y$$$, but this can be tricky to do right. However, there is a neat trick that allows us to solve the problem without any casework. What happens if we change $$$x$$$ into $$$-x$$$? The values of $$$\vert x \vert$$$ and $$$\vert y \vert$$$ stay the same, while $$$\vert x - y \vert$$$ and $$$\vert x + y \vert$$$ will swap values. This means that the pair $$$\{x, y\}$$$ works if and only if $$$\{-x, y\}$$$ works. Similarly we can switch the sign of $$$y$$$. This means that we can replace $$$x$$$ and $$$y$$$ by their absolute values, and the original pair works if and only if the new one works.
If $$$x \ge 0$$$ and $$$y \ge 0$$$ then the condition becomes $$$\vert x - y \vert \le x, y \le x + y$$$. The upper bound obviously always holds, while the lower bound is equivalent by some simple algebra to
$$$$$$x \le 2y \text{ and } y \le 2x$$$$$$
So the problem reduces to counting the number of pairs $$$\{x, y\}$$$ with $$$\vert x \vert \le 2 \vert y \vert$$$ and $$$\vert y \vert \le 2 \vert x \vert$$$. To solve this we now take the absolute values of all the $$$a_i$$$ and sort them into an array $$$b_1 \le b_2 \le \dots \le b_n$$$. The answer to the problem is the number of pairs $$$(l, r)$$$ with $$$l < r$$$ and $$$b_r \leq 2b_l$$$. For each fixed $$$l$$$ we calculate the largest $$$r$$$ that satisfies this condition, and just add $$$r - l$$$ to the answer, as the values $$$l + 1, l + 2, \dots, r$$$ are all the ones that work for this $$$l$$$. We can either do a binary search for the best $$$r$$$ at each $$$l$$$, or calculate the optimal $$$r$$$'s for all of the $$$l$$$'s in $$$\mathcal{O}(n)$$$ using two pointers. Either way, our final complexity is $$$\mathcal{O}(n \log n)$$$ as this is the time required to sort the array.
Complexity: $$$\mathcal{O}(n \log n)$$$