Є N шматків ланцюга, кожен i-й з яких містить Li ланок. Можна розгинати довільні ланки і потім згинать їх знову, з'єднуючи окремі шматки.

Напишіть програму, яка за кількістю шматків ланцюга N та кількості ланок у шматках Li визначає мінімальну кількість ланок, які потрібно разігнути і зігнути знову, щоб з'єднати усі шматки в один ланцюг. Ланцюг не може мати розгалужень, тобто кожна ланка повинна бути з'єднаною з двома ланками (крім двох ланок на краях ланцюга, які повинні бути з'єднані лише з однією ланкою).

Вхідні дані

У першому рядку вхідного файлу знаходиться ціле число N (2 ≤ N ≤ 10000). У другому рядку знаходяться N цілих чисел Li (1 ≤ Li ≤ 1000000000).

Вихідні дані

У єдиному рядку вихідного файлу повинно знаходитись ціле число — найменша кількість ланок, які необхідно розігнути і зігнути знову, щоб отримати один ланцюг з усіх шматків.