← 返回题目列表

Codeforces · 1119/A

A. 伊利亚和多彩的散步

中文机器翻译题面 查看原题

伊利亚生活在美丽的乔达尔斯克市。

Ilya居住的街道上有$$$n$$$栋房屋,从左到右编号为$$$1$$$到$$$n$$$;每两栋相邻房屋之间的距离等于 $$$1$$$ 单位。邻近的房屋为 $$$1$$$ 和 $$$2$$$、$$$2$$$ 和 $$$3$$$、...、$$$n-1$$$ 和 $$$n$$$。房屋 $$$n$$$ 和 $$$1$$$ 不相邻。

房屋的颜色为 $$$c_1, c_2, \ldots, c_n$$$,因此第 $$$i$$$ 房屋的颜色为 $$$c_i$$$。大家都知道乔达尔斯克并不无聊,所以至少有两栋不同颜色的房子。

Ilya 想要选择两栋房子 $$$i$$$ 和 $$$j$$$,使得 $$$1 \leq i < j \leq n$$$,并且它们有不同的颜色:$$$c_i \neq c_j$$$。然后,他将从 $$$i$$$ 房子走到 $$$j$$$ 房子,距离 $$$(j-i)$$$ 个单位。

Ilya 喜欢长途散步,因此他想选择房屋,使它们之间的距离尽可能最大。

帮助 Ilya,找到这个最大可能距离。

输入

第一行包含一个整数 $$$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$$$。

输出

打印一个整数 - Ilya 可以行走的最大可能距离。

示例

输入 #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

注意

在第一个示例中,最佳方式是从第一栋房子步行到最后一栋房子,其中 Ilya 可以步行 $$$5-1 = 4$$$ 单位的距离。

在第二个示例中,最佳方式是从第一所房子步行到第二所房子,或者从第二所房子步行到第三所房子。这两种方式的距离均为 $$$1$$$ 单位。

在第三个示例中,最佳方式是从第三个房子步行到最后一个房子,Ilya 可以步行 $$$7-3 = 4$$$ 单位的距离。