Задача D. Миплы ≡

Условие

На полках сети магазинов настольных игр "Черное и Белое" каждый месяц появляется новая игра. Дизайном миплов (фигурки в виде животных или людей, которые используют как фишки) занимается Тимофей, основной принцип которого — чем реже встречается мипл, там выше он должен быть. По описанию набора фигурок определите их суммарную высоту.

В целях экономии расходного материала, высоты миплов, отличающиеся по количеству от предыдущего, увеличиваются на 1. Высота самого часто встречающегося мипла должна быть равна 1.

Формат входных данных

Первая строка входных данных содержит натуральное число n — количество различных типов миплов. В следующих n строках расположены натуральные числа x_i — количество фигурок i-го типа в наборе для игры, отсортированные по неубыванию.

Формат выходных данных

Выведите одно натуральное число — ответ на вопрос задачи.

Ограничения

1 ≤ n ≤ 10⁵

1 ≤ x_i ≤ 100

Система оценки и описание подзадач

Баллы за каждый тест начисляются независимо.

Решения, верно работающие при n ≤ 2, получат не менее 20 баллов.

Решения, верно работающие на тестах, где все x_i различны, получат не менее 20 баллов.

Пояснение к примерам

В первом примере в наборе для игры используются 24 одинаковых фигурки (как в классических шашках, их цвет в данной задаче не важен). Установив высоту одной шашки равной 1, получим их суммарную высоту 24.

Во втором примере в наборе для игры используются 6 различных типов фигурок (как в шахматах). Для 16 самых часто встречающихся фигур (пешек) установим высоту 1, для трёх следующих типов, встречающихся по 4 раза (кони, слоны и ладьи), установим высоту 2, для двух следующих типов, встречающихся по 2 раза (короли и ферзи), установим высоту 3. Всего получается 16 × 1 + (4 + 4 + 4) × 2 + (2 + 2) × 3 = 16 + 24 + 12 = 52.

Примеры тестов

1
24

24

6
2
2
4
4
4
16

52