Юный тренер покемонов Сергей Б. обнаружил большой дом, состоящий из n квартир, выстроенных в ряд слева направо, причем в каждую квартиру можно зайти с улицы, из каждой квартиры можно выйти на улицу, а также из каждой квартиры можно зайти в соседнюю слева или справа квартиру. Из квартиры номер 1 можно попасть только в квартиру номер 2, а из квартиры номер n можно попасть только в квартиру номер n - 1.

Так сложилось, что в каждой из этих квартир находится ровно один покемон какого-то типа. Возможно, что в каких-то квартирах находятся покемоны одинаковых типов. Сергей Б. попросил жителей дома пустить его к ним в квартиры, чтобы поймать покемонов. Посовещавшись, жители дома решили, что разрешат Сергею Б. зайти с улицы ровно в одну квартиру, посетить несколько квартир, а затем выйти из какой-то квартиры на улицу, причем они не разрешили Сергею Б. посещать никакую квартиру более одного раза.

Сергей Б. очень обрадовался, но как человек интеллигентный, решил посетить как можно меньше квартир, но при этом, естественно, собрать покемонов всех типов, которые есть в доме (иначе зачем тогда это всё). Перед вами стоит задача помочь ему и определить это минимальное число квартир.