Шоколадный должок Так вышло, что Антон должен Саше n шоколадок. Он уже закупил нужное число плиток и решил отдавать их Саше по одной в день; осталось лишь определиться с порядком.
Антон знает, что Саше одинаково нравятся шоколадки всех видов, но с одним исключением: девушка совершенно не радуется шоколадке, если она того же вида, что и накануне. Например, получив 10 горьких Милок подряд, Саша порадуется всего один раз, а вот если они будут чередоваться с карамельными, радости будет в 10 раз больше.
Антону вычислить максимально возможную радость Саши.
Входные данные
В первой строке находится число n (1 ≤ n ≤ 10 5 ) — количество шоколадок. В следующей строке находится n чисел a i (1 ≤ a i ≤ 10 6 ) — виды шоколадок, закупленных Антоном.
Выходные данные
Выведите единственное число — максимально возможную радость Саши.
Примеры
входные данные
5
1 2 3 4 5
выходные данные
5
входные данные
5
3 3 4 3 3
выходные данные
3
входные данные
5
3 3 3 3 3
выходные данные
1
214
453
Ответы на вопрос:
Популярно: Информатика
-
aidosashimbek20005.03.2022 01:29
-
АртемкаЧеловечек15.04.2020 01:22
-
Кей12121.01.2022 03:58
-
Настён198915.05.2020 18:28
-
svr209.06.2022 13:07
-
kriskamai200221.11.2021 16:22
-
МиленаКриницына07.04.2023 00:21
-
skrydyya08.01.2020 02:40
-
xDanielDash15.09.2022 14:54
-
Neymar311019.10.2022 11:09