An Array and Range Additions#224
Sign in

An Array and Range Additions

2 seconds
256 megabytes
Hard

Given an array of integers of length .

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 .

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

  3. Add 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 pairwise distinct.

Input

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

The second line contains integers a_1,a_2,\ldots,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 pairwise distinct.

Examples

Example 1

Loading
Loading

Example 2

Loading
Loading

Example 3

Loading
Loading

Note

In the first example, all elements of the array 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 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 becomes equal to [2,3,1,-2,0,-1,-12,-10,-7].

Scoring

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

  2. ( 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. ( points): n \le 8.

  4. ( points): a_1 = a_n.

  5. ( points): n \le 2000.

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

  7. ( points): no additional constraints.