Ilya and a Colorful Walk

题意翻译

ilya 有很多房子,每个房子都有一个颜色。因为 ilya 喜欢散步,所以想要选最远的两个不同颜色的房子作为散步的起点和终点。输出这个最远距离。 ## 输入格式 第一行一个整数 $n$,表示有多少房子。 第二行 $n$ 个整数,表示颜色,相同的数字表示相同的颜色,不同的数字表示不同的颜色。 ## 输出格式 输出最大距离。

题目描述

Ilya lives in a beautiful city of Chordalsk. There are $ n $ houses on the street Ilya lives, they are numerated from $ 1 $ to $ n $ from left to right; the distance between every two neighboring houses is equal to $ 1 $ unit. The neighboring houses are $ 1 $ and $ 2 $ , $ 2 $ and $ 3 $ , ..., $ n-1 $ and $ n $ . The houses $ n $ and $ 1 $ are not neighboring. The houses are colored in colors $ c_1, c_2, \ldots, c_n $ so that the $ i $ -th house is colored in the color $ c_i $ . Everyone knows that Chordalsk is not boring, so there are at least two houses colored in different colors. Ilya wants to select two houses $ i $ and $ j $ so that $ 1 \leq i < j \leq n $ , and they have different colors: $ c_i \neq c_j $ . He will then walk from the house $ i $ to the house $ j $ the distance of $ (j-i) $ units. Ilya loves long walks, so he wants to choose the houses so that the distance between them is the maximum possible. Help Ilya, find this maximum possible distance.

输入输出格式

输入格式


The first line contains a single integer $ n $ ( $ 3 \leq n \leq 300\,000 $ ) — the number of cities on the street. The second line contains $ n $ integers $ c_1, c_2, \ldots, c_n $ ( $ 1 \leq c_i \leq n $ ) — the colors of the houses. It is guaranteed that there is at least one pair of indices $ i $ and $ j $ so that $ 1 \leq i < j \leq n $ and $ c_i \neq c_j $ .

输出格式


Print a single integer — the maximum possible distance Ilya can walk.

输入输出样例

输入样例 #1

5
1 2 3 2 3

输出样例 #1

4

输入样例 #2

3
1 2 1

输出样例 #2

1

输入样例 #3

7
1 1 3 1 1 1 1

输出样例 #3

4

说明

In the first example the optimal way is to walk from the first house to the last one, where Ilya can walk the distance of $ 5-1 = 4 $ units. In the second example the optimal way is to either walk from the first house to the second or from the second to the third. Both these ways have the distance of $ 1 $ unit. In the third example the optimal way is to walk from the third house to the last one, where Ilya can walk the distance of $ 7-3 = 4 $ units.