P12568 [UOI 2023] An Array and Range Additions

给定一个长度为 $n$ 的整数数组 $a$。 你可以通过**加法操作**来修改数组。要执行**加法操作**，你需要依次完成以下三个步骤： - 选择任意整数 $x$。 - 选择数组中的任意子数组 $[l;r]$。 - 将 $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$ 中所有元素两两不同的最小**加法操作**次数。

在第一个样例中，数组 $a$ 的所有元素已经是两两不同的。 在第二个样例中，应用两次**加法操作**，参数分别为 $x=-3$、$l=1$、$r=2$ 和 $x=-1$、$l=1$、$r=3$ 后，数组 $a$ 变为 $[-2, -1, 1, 3, 2]$。 在第三个样例中，应用两次**加法操作**，参数分别为 $x=-3$、$l=4$、$r=8$ 和 $x=-10$、$l=7$、$r=9$ 后，数组 $a$ 变为 $[2, 3, 1, -2, 0, -1, -12, -10, -7]$。 ### 评分标准 - （$9$ 分）：数组 $a$ 的所有元素均为 $1$。 - （$15$ 分）：对于 $1 \le i \le n$，$1 \le a_i \le 2$；对于 $1 \le i < n$，$a_i \le a_{i+1}$。 - （$14$ 分）：$n \le 8$。 - （$17$ 分）：$a_1 = a_n$。 - （$12$ 分）：$n \le 2000$。 - （$12$ 分）：对于 $1 \le i \le n$，$1 \le a_i \le 100$。 - （$21$ 分）：无额外限制。 翻译由 DeepSeek V3 完成