На свій перший день народження Меґґі Сімпсон, персонаж мультсеріалу «Сімпсони», отримала в подарунок конструктор: ігровий набір, що складається з паличок різної довжини. Кінці паличок можна скріплювати, причому з’єднані таким чином палички можуть утворювали довільний ненульовий кут, крім розгорнутого (180°).

Меґґі хоче скласти опуклий многокутник, використавши якомога більшу кількість паличок із конструктора як сторони цього багатокутника.

Напишіть програму, що за розмірами паличок у конструкторі визначить, чи вдасться Меґґі скласти із паличок опуклий многокутник, і якщо вдасться, то визначить, яку найбільшу кількість паличок вона зможе для цього використати.

Вхідні дані

У першому рядку вказано кількість $N$ ($2$ ≤ 4N4 ≤ $10^5$) паличок у наборі. У другому рядку записано N натуральних чисел, менших за $10^9$ (не обов’язково попарно різних) - довжини паличок.

Вихідні дані

Вивести одне число - найбільшу кількість паличок з набору, із яких можна скласти опуклий многокутник, або число $0$, якщо скласти опуклий многокутник не вдасться.