Любимая геометрическая фигура дочерей Грю — треугольник. В свободное от занятий и помощи Грю в его злодействах время девочки любят играть в следующую игру: каждая из них выбирает целое положительное число и после этого они вместе проверяют, может ли существовать невырожденный треугольник со сторонами, имеющими длины, равные выбранным числам.
В какой-то момент нашли дома набор из $$$n$$$ положительных целых чисел $$$a$$$. Они хотят узнать, сколько существует целых $$$x$$$ таких, что $$$x$$$ и любые два другие числа из набора $$$a$$$ всегда будут являться длинами сторон некоторого невырожденного треугольника. Помогите девочкам решить эту задачу.
В первой строке входных данных дано одно целое число — $$$n$$$ ($$$2 \le n \le 5 \cdot 10^5$$$).
Во второй строке входных данных дно $$$n$$$ целых чисел — числа набора $$$a$$$ ($$$1 \le a_i \le 10^9$$$).
Выведите одно целое число — ответ на вопрос задачи.
Баллы за каждую подзадачу начисляются только в случае, если все тесты для этой подзадачи и необходимых подзадач успешно пройдены.
| Подзадача | Баллы | Ограничения | Необходимые подзадачи | Информация о проверке |
| 0 | – | примеры из условия | полная | |
| 1 | 14 | $$$n \le 500$$$; $$$a_i \le 200$$$ для всех $$$i$$$ | 0 | полная |
| 2 | 15 | $$$n \le 2000$$$; $$$a_i \le 500$$$ для всех $$$i$$$ | 0, 1 | первая ошибка |
| 3 | 11 | $$$a_i \le 4$$$ для всех $$$i$$$ | первая ошибка | |
| 4 | 13 | $$$a_i = a_j$$$ для всех $$$i$$$ и $$$j$$$ | первая ошибка | |
| 5 | 14 | $$$a_1 = 1$$$ | первая ошибка | |
| 6 | 16 | $$$a_i \le 2 \cdot 10^5$$$ для всех $$$i$$$ | 0, 1, 2, 3 | первая ошибка |
| 7 | 17 | без дополнительных ограничений | 0 – 6 | первая ошибка |
33 3 5
3
33 1 2
0
59 5 6 7 9
6