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

你可以使用加法操作来修改数组。执行一次加法操作需要依次进行以下三个步骤：

1. 选择任意整数 $x$。
2. 选择数组的任意子数组 $[l; r]$。
3. 将 $x$ 加到所选子数组的每个元素上（执行赋值操作 $a_i \leftarrow (a_i + x)$，其中 $l \le i \le r$）。

求使得数组 $a$ 中所有元素互不相同所需的最少加法操作次数。

输入格式

第一行包含一个整数 $n$ ($1 \le n \le 2 \cdot 10^5$) —— 数组的长度。 第二行包含 $n$ 个整数 $a_1, a_2, \dots, a_n$ ($1 \le a_i \le 10^9$) —— 数组的元素。

输出格式

输出一个整数 —— 使得数组 $a$ 中所有元素互不相同所需的最少加法操作次数。

样例

输入格式 1

3
1 2 3

输出格式 1

0

说明

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

子任务

1. (9 分)：数组 $a$ 的所有元素均等于 1。
2. (15 分)：对于 $1 \le i \le n$，$1 \le a_i \le 2$；对于 $1 \le i < n$，$a_i \le a_{i+1}$。
3. (14 分)：$n \le 8$。
4. (17 分)：$a_1 = a_n$。
5. (12 分)：$n \le 2000$。
6. (12 分)：对于 $1 \le i \le n$，$1 \le a_i \le 100$。
7. (21 分)：无附加限制。