题目描述

在一个被称为"彩虹街"的小镇上，有一条街道上有 $n$ 栋房子，这些房子按照从左到右的顺序依次编号为 $1$ 到 $n$。

每栋房子都被粉刷了一种颜色，用 $colors_i$ 来代表第 $i$ 栋房子被粉刷的颜色。

你的任务是找出两栋颜色不同的房子之间的最大距离，并输出这个最大距离。

这里的两栋房子之间的距离，指的是它们的编号之差的绝对值。

输入格式

• 第一行输入一个整数表示房子的个数 $n$。
• 第二行输入 $n$ 栋房子的颜色 $colors_1, colors_2, dots, colors_n$。

输出格式

• 输出两栋颜色不同房子之间的最大距离。

样例

7
1 1 1 6 1 1 1

3

5
1 8 3 8 3

4

20
3 3 3 2 2 2 2 2 2 2 3 3 3 3 3 3 2 3 3 3

16

提示

样例 1 解释：有 $7$ 栋房子的颜色分别为：$1, 1, 1, 6, 1, 1, 1$，其中第 $1$ 座房子和第 $4$ 栋房子颜色不同，且距离最远，最远距离为 $4-1=3$。

数据范围

• 对于 $20\%$ 的数据，满足 $1 \le n \le 2000$；
• 对于 $100\%$ 的数据，满足 $2 \le n \le 10^5$，$0 \le colors_i \le 10^5$，且至少存在 $2$ 栋颜色不同的房子。