eolymp
bolt
Try our new interface for solving problems
Problems

Конфетная лотерея

Конфетная лотерея

Time limit 1 second
Memory limit 64 MiB

Перед началом І открытого Кубка Александрии организаторы решили провести лотерею! Основным элементом лотереи есть Nбочёнков, находящихся в мешке. На каждом бочёнке написано некоторое целое число A_i. Числа, написанные на бочёнках разные.

В Кубке принимает участие N-1 участник. Каждый из N-1 участников по очереди подходит к организаторам и достает из мешка два бочёнка. Из двух выбранных бочёнков каждый участник оставляет себе тот бочёнок, на котором написано большее число, а второй бочёнок возвращает обратно в мешок. Очевидно, что после того, как все участники выберут себе бочёнки, в мешке останется ровно один бочёнок.

По завершению должна быть праздничная часть – раздача конфет. Каждый участник получает конфеты. Количество полученных участником конфет соответствует числу, написанном на бочёнке, который этот участник оставил себе.

Впрочем, перед организаторами возникла непростая задача – какое число конфет может понадобится для лотереи? Ваша задача помочь организаторам посчитать максимально возможное количество конфет, которое могут выиграть все участники.

Input data

Первая строка содержит одно целое число N– количество бочёнков (2 ≤ N ≤ 100). Во второй строке находится Nцелых разных чисел A_i (1 ≤ A_i ≤ 32767). Числа разделены одиночными пробелами.

Output data

Одно целое число – максимально возможное количество конфет, которое могут получить все участники.

Examples

Input example #1
2
1 100
Output example #1
100