Так вышло, что Гриша должен Маше N шоколадок. Он закупил нужное количество плиток разных видов, решил отдавать Маше по одной в день, и ему осталось лишь определиться с порядком.

Гриша знает, что Маша одинаково радуется шоколадке любого вида, с одним лишь исключением: она совершенно не радуется шоколадке, если она имеет тот же вид, что и накануне. Например, получив 10 шоколадок одного вида подряд, Маша порадуется всего один раз, а вот если одни будут хотя бы двух чередующихся типов — радости будет в 10 раз больше.

Помогите Грише вычислить максимально возможную радость Маши.