В каком-то другом мире сегодня 29 декабря. Дарёна с дедом Кокованей решили купить N товаров в универмаге для веселого празднования Нового года. Обычная цена i-го товара (1 <= i <= N) - pi серебряных камушек, причем pi всегда чётное. У деда Коковани есть купон на скидку, и он может купить один товар по самой высокой цене за половину обычной цены. Оставшиеся N − 1 позиции стоят по своей обычной цене. Сколько раз необходимо ударить Серебряному копытцу, чтобы Дарёна с дедом могли расплатиться за товар? За один удар из под копытца вылетает один серебреный камушек.
Входные данные
В первой строке задано целое число N (2 <= N <= 105). В следующих N строках расположены целые положительные четные числа pi (100 <= pi <= 106), каждое число в отдельной строке.
Выходные данные
Выведите на экран ответ на задачу.