#212629. [UOI 2023] An Array and Range Additions

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:

• Choose any integer .
• Choose any subarray of the array.
• Add to each element of the chosen subarray (perform the assignment operation for ).

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

The first line contains a single integer () --- the length of the array.

The second line contains integers () --- the elements of the array.

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

样例输入 1

3
1 2 3

样例输出 1

0

样例输入 2

5
2 3 2 3 2

样例输出 2

2

样例输入 3

9
2 3 1 1 3 2 1 3 3

样例输出 3

2

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

In the second example, after applying two \textit{addition operations} with parameters , , and , , , the array becomes equal to .

In the third example, after applying two \textit{addition operations} with parameters , , and , , , the array becomes equal to .

Scoring

• ( points): all elements of the array are equal to .
• ( points): for ; for .
• ( points): .
• ( points): .
• ( points): .
• ( points): for .
• ( points): no additional constraints.