| Codeforces Round 561 (Div. 2) |
|---|
| Закончено |
В легенде об образовании Векторляндии говорится о двух целых числах $$$x$$$ и $$$y$$$. Несколько веков назад король массивов поставил две отметки в точки $$$|x|$$$ и $$$|y|$$$ на числовой прямой, захватил всю землю между ними (включая границы) и назвал ее Массивляндией. Спустя много лет король векторов поставил две отметки в точки $$$|x - y|$$$ и $$$|x + y|$$$, захватил всю землю между ними (включая границы) и назвал ее Векторляндией. Все знают, что вся земля Массивляндии лежала внутри или на границе Векторляндии.
Выражение $$$|z|$$$ обозначает абсолютное значение числа $$$z$$$.
На экзамене по истории Жозе попался следующий вопрос: «Каковы значения $$$x$$$ и $$$y$$$?». Жозе не знает ответа на этот вопрос, но он думает, что сузил количество вариантов ответа до $$$n$$$ целых чисел $$$a_1, a_2, \dots, a_n$$$. Он хочет узнать число таких неупорядоченных пар двух различных чисел из этих $$$n$$$, что легенда могла быть верной, если $$$x$$$ и $$$y$$$ были равны этим числам. Возможно также, что Жозе неправ и никакая пара чисел не удовлетворяет легенде.
Первая строка содержит одно целое число $$$n$$$ ($$$2 \le n \le 2 \cdot 10^5$$$) — количество вариантов.
Вторая строка содержит $$$n$$$ различных целых чисел $$$a_1, a_2, \dots, a_n$$$ ($$$-10^9 \le a_i \le 10^9$$$) — варианты, которые рассматривает Жозе.
Выведите одно целое число — число различных неупорядоченных пар $$$\{x, y\}$$$, выбранных из вариантов Жозе, которые не противоречат легенде.
3 2 5 -3
2
2 3 6
1
Рассмотрим первый пример. Для пары $$$\{2, 5\}$$$ ситуация показана на рисунке ниже. Границы Массивляндии находятся в точках $$$|2| = 2$$$ и $$$|5| = 5$$$, а границы Векторляндии — в точках $$$|2 - 5| = 3$$$ и $$$|2 + 5| = 7$$$:
Видно, что такой случай противоречит легенде, потому что земля в отрезке $$$[2, 3]$$$ не принадлежит Векторляндии. Для пары чисел $$$\{5, -3\}$$$ ситуация показана на рисунке ниже. Массивляндия находится на отрезке $$$[3, 5]$$$, а Векторляндия — на отрезке $$$[2, 8]$$$:
В этом случае противоречия легенде нет, ведь Векторляндия полностью содержит Массивляндию. Можно также показать, что нет противоречия легенде и для пары $$$\{2, -3\}$$$, то есть всего для двух пар.
Во втором примере единственно возможная пара — это $$$\{3, 6\}$$$, и легенда выглядит так:
Обратите внимание, несмотря на то, что Массивляндия и Векторляндия имеют общую границу в точке $$$3$$$, мы все равно считаем, что Массивляндия лежит полностью внутри Векторляндии.
