Konstruktor

Məggi Simpsona, "Simpsonlar" cizgi filmindəki bir xarakter, ilk doğum günündə hədiyyə olaraq müxtəlif uzunluqlarda çubuqlardan ibarət bir konstruktor dəsti aldı. Bu çubuqların ucları birləşdirilə bilər və belə birləşdirilmiş çubuqlar istənilən sıfır olmayan bucağı, lakin düz bucağı (180°) təşkil edə bilməz.

Məggi bu çubuqlardan mümkün qədər çoxunu istifadə edərək qabarıq çoxbucaqlı yaratmaq istəyir.

Çubuqların uzunluqlarına əsasən, Məgginin bu çubuqlardan qabarıq çoxbucaqlı düzəldə biləcəyini və əgər mümkündürsə, bunun üçün ən çox neçə çubuq istifadə edə biləcəyini müəyyən edən bir proqram yazın.

Giriş məlumatları

Birinci sətirdə dəstdəki çubuqların sayı $N$ ($2\le N\le 10^5$) verilir. İkinci sətirdə $N$ təbii ədəd, $10^9$-dan kiçik (mütləq fərqli olmaya bilər) - çubuqların uzunluqları göstərilir.

Çıxış məlumatları

Bir ədəd çıxarın - dəstdəki çubuqlardan qabarıq çoxbucaqlı düzəltmək üçün istifadə edilə biləcək ən çox çubuq sayı, əgər qabarıq çoxbucaqlı düzəltmək mümkün deyilsə, $0$ ədədi.

Nümunələr