Определим циклическую последовательность размера \(n\) как массив \(s\) длины \(n\), в котором \(s_n\) является соседним с \(s_1\).
У Muxii есть кольцо, представленное циклической последовательностью \(a\) размера \(n\).
Сама сущность кольца ненавидит равные соседние элементы. Поэтому, если два соседних элемента в последовательности равны в любой момент времени, один из них будет немедленно стерт. Изначально последовательность не содержит равных соседних элементов.
Muxii может выполнять следующие операции, пока последовательность не станет пустой:
- Выбрать элемент в \(a\) и стереть его.
Например, если кольцо имеет вид \([1, 2, 4, 2, 3, 2]\), и Muxii стирает элемент \(4\), то кольцо сотрёт один из элементов, равных \(2\), и кольцо примет вид \([1, 2, 3, 2]\).
Muxii хочет найти максимальное количество операций, которые он может выполнить.
Заметим, что в кольце размером \(1\) его единственный элемент не считается соседним с самим собой (поэтому он не стирается сразу).
Примечание
В первом наборе входных данных вы можете сначала стереть второй элемент, а затем стереть оставшиеся элементы по одному в любом порядке. Всего можно выполнить эту операцию \(4\) раза. Обратите внимание, что если сначала стереть первый элемент, то последовательность превратится в \([2,3,2]\), а затем сразу станет \([2,3]\).
Во втором наборе входных данных можно сначала стереть первый элемент, тогда последовательность превратится в \([2,1]\). Затем можно стереть все оставшиеся элементы по одному в любом порядке.