На свой первый день рождения Мэгги Симпсон, персонаж мультсериала "Симпсоны", получила в подарок конструктор: игровой набор, который состоит из палочек различной длины. Концы палочек можно скреплять, причем соединенные таким образом палочки могут образовывать произвольный ненулевой угол, кроме развернутого (180°).
Мэгги хочет сложить выпуклый многоугольник, использовав как можно большее количество палочек из конструктора как стороны этого многоугольника.
Напишите программу, которая по размерам палочек в конструкторе определит, удастся ли Мэгги сложить из палочек выпуклый многоугольник, и если удастся, то определит, какое наибольшее количество палочек она сможет для этого использовать.
ВвідВ первой строке указано количество N (2 ≤ N ≤ 105) палочек в наборе. Во второй строке записаны N натуральных чисел, меньших 109 (не обязательно попарно различных) - длины палочек.
ВивідВывести одно число - наибольшее количество палочек из набора, из которых можно сложить выпуклый многоугольник, или число 0, если сложить выпуклый многоугольник не получится.