Codeforces Round 561 (Div. 2) |
---|

Finished |

Virtual contest is a way to take part in past contest, as close as possible to participation on time. It is supported only ICPC mode for virtual contests.
If you've seen these problems, a virtual contest is not for you - solve these problems in the archive.
If you just want to solve some problem from a contest, a virtual contest is not for you - solve this problem in the archive.
Never use someone else's code, read the tutorials or communicate with other person during a virtual contest.

binary search

sortings

two pointers

*1500

No tag edit access

The problem statement has recently been changed. View the changes.

×
C. A Tale of Two Lands

time limit per test

1 secondmemory limit per test

256 megabytesinput

standard inputoutput

standard outputThe 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

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

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.

Examples

Input

3 2 5 -3

Output

2

Input

2 3 6

Output

1

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.

Codeforces (c) Copyright 2010-2023 Mike Mirzayanov

The only programming contests Web 2.0 platform

Server time: Dec/05/2023 05:16:11 (l3).

Desktop version, switch to mobile version.

Supported by

User lists

Name |
---|