A. Илья и красочная прогулка
ограничение по времени на тест
2 секунды
ограничение по памяти на тест
256 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

Илья живет в прекрасном городе Хордальске.

На его улице расположено $$$n$$$ домов, пронумерованных по порядку от $$$1$$$ до $$$n$$$, причем расстояние между двумя соседними домами равно $$$1$$$. Соседними домами являются $$$1$$$ и $$$2$$$, $$$2$$$ и $$$3$$$, ..., $$$n-1$$$ и $$$n$$$. Дома $$$n$$$ и $$$1$$$ соседними не являются.

Дома покрашены в цвета $$$c_1, c_2, \ldots, c_n$$$, то есть $$$i$$$-й дом покрашен в цвет $$$c_i$$$. Известно, что Хордальск не является скучным городом, поэтому найдутся хотя бы два дома, покрашенные в разные цвета.

Илья хочет выбрать два дома $$$i$$$ и $$$j$$$ таких, что $$$1 \leq i < j \leq n$$$, а цвета этих домов отличаются: $$$c_i \neq c_j$$$. Затем он пройдет от дома $$$i$$$ до дома $$$j$$$ расстояние $$$(j-i)$$$.

Илье нравятся долгие прогулки, поэтому он хочет выбрать дома так, чтобы пройденное им расстояние было максимально возможным.

Помогите Илье, найдите, чему равно это максимальное расстояние.

Входные данные

В первой строке записано одно целое число $$$n$$$ ($$$3 \leq n \leq 300\,000$$$) — количество домов на улице Ильи в Хордальске.

Во второй строке записаны $$$n$$$ целых чисел, разделенных пробелами $$$c_1, c_2, \ldots, c_n$$$ ($$$1 \leq c_i \leq n$$$) — цвета домов на описываемой улице.

Гарантируется, что найдется хотя бы одна пара $$$i$$$ и $$$j$$$ такая, что $$$1 \leq i < j \leq n$$$ и $$$c_i \neq c_j$$$.

Выходные данные

Выведите одно целое число — максимально возможное расстояние, которое может пройти Илья за одну прогулку.

Примеры
Входные данные
5
1 2 3 2 3
Выходные данные
4
Входные данные
3
1 2 1
Выходные данные
1
Входные данные
7
1 1 3 1 1 1 1
Выходные данные
4
Примечание

В первом примере оптимальным является маршрут от первого дома до последнего, в котором Илья пройдет расстояние, равное $$$5-1 = 4$$$.

Во втором примере оптимальным является либо маршрут от первого дома до второго, либо от второго до третьего. Оба этих маршрута имеют расстояние, равное $$$1$$$.

В третьем примере оптимальным является маршрут от третьего дома до последнего, на котором Илья пройдет расстояние $$$7-3 = 4$$$.