Решение задачи Илья и красочная прогулка с Codeforces

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

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

Дома покрашены в цвета c1,c2,…,cn, то есть i-й дом покрашен в цвет ci. Известно, что Хордальск не является скучным городом, поэтому найдутся хотя бы два дома, покрашенные в разные цвета.

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

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