题目描述

给定一个长度为 $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$ 中所有元素两两不同的最小加法操作次数。

3
1 2 3

0

5
2 3 2 3 2

2

9
2 3 1 1 3 2 1 3 3

2

提示

在第一个样例中，数组 $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 完成