[AdditionalFile5220.zip](file://AdditionalFile5220.zip?type=additional_file)

#5220. 「UOI 2023 Stage 4 Day1」数组与区间加法

标签: 传统 | 时间限制: 2000 ms | 内存限制: 256 MiB |

题目描述

题目译自 Ukrainian Olympiads in Informatics 2023 Stage 4 Day1 T3. Масив і додавання на відрізку

给定一个长度为 $n$ 的整数数组 $a$。

你可以通过加法操作来修改数组。为了执行一次加法操作，需要按照以下三个步骤进行：

1. 选择一个任意整数 $x$；
2. 选择数组的一个任意子区间 $[l, r]$；
3. 将选定子区间内的每个元素加上 $x$（即对 $l \le i \le r$ 执行操作 $a_i \leftarrow (a_i + x)$）。

找出使数组 $a$ 的所有元素两两不同所需的最小加法操作次数。

输入格式

输入的第一行包含一个整数 $n$ $(1 \le n \le 2 \cdot 10^5)$，表示数组的长度。

第二行包含 $n$ 个整数 $a_1, a_2, \ldots, a_n$ $(1 \le a_i \le 10^9)$，表示数组的元素。

输出格式

输出一个整数，表示使数组 $a$ 的所有元素两两不同所需的最小加法操作次数。

样例 1

输入

3
1 2 3

输出

0

在第一个样例中，数组 $a$ 的所有元素已经是两两不同的。

样例 2

输入

5
2 3 2 3 2

输出

2

在第二个样例中，通过执行两次加法操作，参数分别为 $x=-3$，$l=1$，$r=2$ 和 $x=-1$，$l=1$，$r=3$，数组 $a$ 变为 $[-2, -1, 1, 3, 2]$。

样例 3

输入

9
2 3 1 1 3 2 1 3 3

输出

2

在第三个样例中，通过执行两次加法操作，参数分别为 $x=-3$，$l=4$，$r=8$ 和 $x=-10$，$l=7$，$r=9$，数组 $a$ 变为 $[2, 3, 1, -2, 0, -1, -12, -10, -7]$。

数据范围与提示

详细子任务附加限制及分值如下表所示：