Martin 邀请了他认识的所有人来庆祝他的 535 岁生日，共有 $n$ 位来自世界各地的客人接受了邀请。

在决定座位安排时，Martin 的母亲 Margarethe 决定所有客人都应该以“最大程度的尴尬”入座；这是为了确保客人在晚餐期间没有任何有意义的话题可以讨论，从而每个人都能安静地享用她那美味的香菜汤（正如俗话所说：“当食物美味时，谈话就会消亡”）。

CC0, by strecosa via Pixabay

Margarethe 知道，如果客人们沿着一张长桌排成一排入座，且没有任何人与说同一种语言的人相邻，那么尴尬程度就会达到最大。更进一步，她将座位安排的尴尬程度定义为：说同一种语言的任意两位客人之间所隔的最少座位数。如果没有任何两位客人说同一种语言，则尴尬程度定义为 $n$（客人的总数）。相邻的两个座位被认为相隔 1。

给定一个座位安排中每位客人所说的语言，你能帮助 Margarethe 确定该安排的尴尬程度吗？

输入格式

第一行包含一个整数 $n$ ($1 \le n \le 100\,000$)，表示客人的数量。第二行包含 $n$ 个整数，其中第 $i$ 个整数 $x_i$ ($0 \le x_i \le 10^9$) 表示坐在第 $i$ 个位置的客人所说的语言（每位客人恰好说一种语言）。

输出格式

一个整数，表示该座位安排的尴尬程度。

样例

输入格式 1

4
1 2 3 1

输出格式 1

3

输入格式 2

3
1 2 3

输出格式 2

3