An Array and Range Additions

Given an array of integers $a$ of length $n$.

You can modify the array using the addition operation. To apply the addition operation, you need to perform three sequential actions:

1. Choose any integer $x$.

2. Choose any subarray $[l;r]$ of the array.

3. Add $x$ to each element of the chosen subarray (perform the assignment operation $a_i\leftarrow (a_i+x)$ for $l\le i\le r$).

Find the minimum number of addition operations required to make all elements of the array $a$ pairwise distinct.

Input

The first line contains a single integer $n$ ($1\le n\le 2\cdot 10^5$) — the length of the array.

The second line contains $n$ integers $a_1,a_2,\dots ,a_n$ ($1\le a_i\le 10^9$) — the elements of the array.

Output

Output a single integer — the minimum number of addition operations required to make all elements of the array $a$ pairwise distinct.

Examples

Note

In the first example, all elements of the array $a$ are pairwise distinct.

In the second example, after applying two addition operations with parameters $x=-3$, $l=1$, $r=2$ and $x=-1$, $l=1$, $r=3$, the array $a$ becomes equal to $[-2,-1,1,3,2]$.

In the third example, after applying two addition operations with parameters $x=-3$, $l=4$, $r=8$ and $x=-10$, $l=7$, $r=9$, the array $a$ becomes equal to $[2,3,1,-2,0,-1,-12,-10,-7]$.

Scoring

1. ($9$ points): all elements of the array $a$ are equal to $1$.

2. ($15$ points): $1\le a_i\le 2$ for $1\le i\le n$; $a_i\le a_{i+1}$ for $1\le i<n$.

3. ($14$ points): $n\le 8$.

4. ($17$ points): $a_1=a_n$.

5. ($12$ points): $n\le 2000$.

6. ($12$ points): $1\le a_i\le 100$ for $1\le i\le n$.

7. ($21$ points): no additional constraints.