# Problem D

Awkward Party

Martin has invited everyone he knows to celebrate his 535th birthday, and a whopping $n$ people from all over the world have accepted the invitation.

When deciding the seating arrangement, Martin’s mother
Margarethe have decided that all the guests should be seated
with *maximum awkwardness*; this is to ensure that
nobody has anything meaningful to discuss during dinner, and
everyone would instead silently enjoy her rather tasty
coriander soup (as the saying goes; “when the food is good,
conversation dies”).

Margarethe knows that awkwardness is maximized if the guests
are seated in a long row along a single table, in such a way
that nobody sits next to someone speaking the same language as
themselves. Better yet, she has defined the *awkwardness
level* of a seating arrangement to be the minimum number of
seats separating any two guests speaking the same language. If
no two people speak the same language, the awkwardness level is
defined to be $n$ (the
number of guests). Two seats next to each other are said to be
separated by $1$.

Given the languages spoken in a proposed seating arrangement, can you help Margarethe determine the awkwardness level?

## Input

The first line contains an integer $n$ ($1 \leq n \leq 100\, 000$) denoting the number of guests. On the second line follows $n$ integers, the $i$’th of which $x_ i$ ($0 \leq x_ i \leq 10^9$) indicating the language spoken by the guest seated at position $i$ in the proposed arrangement (each guest speaks exactly one language).

## Output

A single integer, the awkwardness level of the proposed seating arrangement.

Sample Input 1 | Sample Output 1 |
---|---|

4 1 2 3 1 |
3 |

Sample Input 2 | Sample Output 2 |
---|---|

3 1 2 3 |
3 |