Задача №112114. Конструктор
На свой первый день рождения Мэгги Симпсон, персонаж мультсериала «Симпсоны», получила в подарок конструктор: игровой набор, который состоит из палочек различной длины. Концы палочек можно скреплять, причем соединенные таким образом палочки могут образовывать произвольный ненулевой угол, кроме развернутого. Мэгги хочет сложить выпуклый многоугольник, использовав как можно большее количество палочек из конструктора как стороны этого многоугольника.
Напишите программу, которая по размерам палочек в конструкторе определит, удастся ли Мэгги сложить из палочек выпуклый многоугольник, и если удастся, то определит, какое наибольшее количество палочек она сможет для этого использовать.
В первой строке входного файла указано количество N палочек в наборе, 2 ≤ N ≤ 10 5 . Во второй строке записаны N натуральных чисел, меньших 10 9 (не обязательно попарно различных) — длины палочек.
Выходной файл должен содержать единственное число — наибольшее количество палочек из набора, из которых можно сложить выпуклый многоугольник, или число 0 , если сложить выпуклый многоугольник не получится.
4 5 1000 5 5
3
3 1 2 3
0