PomogiSPb

03.08.2021 14:21

Информатика

Есть ответ 👍

Шоколадный должок Так вышло, что Антон должен Саше 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