ახალი წელი ბავშვების საყვარელი დღესასწაულია, რადგან ყოველ ახალ წელს თოვლის ბაბუა მათ საჩუქრებს ჩუქნის. თუმცა მანამ, სანამ ყველა ბავშვი კუთვნილ საჩუქარს მიიღებს, თოვლის ბაბუას მძიმე სამუშაო აქვს შესასრულებელი: 

 ლაპლანდიის სახელოსნოში ერთ რიგად არის დალაგებული N ცალი სათამაშო. სათამაშოები ერთმანეთისგან ხარისხით განსხვავდება, რაც ნატურალური რიცხვების სახით არის წარმოდგენილი (რაც მეტია მისი რიცხვითი მნიშვნელობა, მით უფრო კარგი ხარისხის არის სათამაშო). თოვლის ბაბუა საჩუქრებს შემდეგი წესების დაცვით ამზადებს: 

• ყოველი საჩუქარი ერთი ან მეტი ერთმანეთის მომდევნო სათამაშოსგან უნდა შედგებოდეს;

• საჩუქრები არ უნდა თანაიკვეთებოდნენ, ყოველი სათამაშო მაქსიმუმ ერთი საჩუქრის შემადგენლობაში უნდა შედიოდეს;

• ყოველ საჩუქარში შემავალი სათამაშოების ჯამური ხარისხი უნდა იყოს ტოლი. 

 თქვენი მიზანია, ამ წესების დაცვით რაც შეიძლება მეტი საჩუქარი დაამზადებინოთ თოვლის ბაბუას. 

შესატანი მონაცემები: პირველ ხაზზე შემოდის მთელი რიცხვი N (1 ≤ N ≤ 1500) - სათამაშოების რაოდენობა. მეორე ხაზზე შემოდის N ცალი მთელი რიცხვი a[1], a[2], …, a[N] (1 ≤ a_i ≤ 10⁵) - სათამაშოების ხარისხები. 

 გამოსატანი მონაცემები: გამოიტანეთ მთელი რიცხვი M - მაქსიმუმ რამდენი საჩუქრის დამზადება შეუძლია თოვლის ბაბუას. 

მაგალითები

შესატანი მონაცემები
7
4 1 2 2 1 5 3 
                  დაკოპირება

გამოსატანი მონაცემები
3
                  დაკოპირება

შესატანი მონაცემები
4
1 1 1 1
                  დაკოპირება

გამოსატანი მონაცემები
4
                  დაკოპირება

შენიშვნა

ამოცანის პირობა და ტესტები მოგვაწოდა სტეფანე გურგენიძემ.