Треугольники
ограничение по времени на тест
1 секунда
ограничение по памяти на тест
256 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

Любимая геометрическая фигура дочерей Грю — треугольник. В свободное от занятий и помощи Грю в его злодействах время девочки любят играть в следующую игру: каждая из них выбирает целое положительное число и после этого они вместе проверяют, может ли существовать невырожденный треугольник со сторонами, имеющими длины, равные выбранным числам.

В какой-то момент нашли дома набор из $$$n$$$ положительных целых чисел $$$a$$$. Они хотят узнать, сколько существует целых $$$x$$$ таких, что $$$x$$$ и любые два другие числа из набора $$$a$$$ всегда будут являться длинами сторон некоторого невырожденного треугольника. Помогите девочкам решить эту задачу.

Входные данные

В первой строке входных данных дано одно целое число — $$$n$$$ ($$$2 \le n \le 5 \cdot 10^5$$$).

Во второй строке входных данных дно $$$n$$$ целых чисел — числа набора $$$a$$$ ($$$1 \le a_i \le 10^9$$$).

Выходные данные

Выведите одно целое число — ответ на вопрос задачи.

Система оценки

Баллы за каждую подзадачу начисляются только в случае, если все тесты для этой подзадачи и необходимых подзадач успешно пройдены.

ПодзадачаБаллыОграничения Необходимые подзадачи Информация о проверке
0примеры из условияполная
114$$$n \le 500$$$; $$$a_i \le 200$$$ для всех $$$i$$$0полная
215$$$n \le 2000$$$; $$$a_i \le 500$$$ для всех $$$i$$$0, 1первая ошибка
311$$$a_i \le 4$$$ для всех $$$i$$$первая ошибка
413$$$a_i = a_j$$$ для всех $$$i$$$ и $$$j$$$первая ошибка
514$$$a_1 = 1$$$первая ошибка
616$$$a_i \le 2 \cdot 10^5$$$ для всех $$$i$$$0, 1, 2, 3первая ошибка
717без дополнительных ограничений0 – 6первая ошибка

Примеры

Входные данные
3
3 3 5
Выходные данные
3
Входные данные
3
3 1 2
Выходные данные
0
Входные данные
5
9 5 6 7 9
Выходные данные
6