题目描述

给定一个长度为 $n$ 的数列 $a_1, a_2, \ldots, a_n(1 \le a_i \le n)$。

你可以对这个数列进行任意次操作。

每次操作，你可以选择任意一个整数 $x$，然后将数列 $a$ 中所有数值等于 $x$ 的 $a_i$ 都置为 $0$（即对于任意 $1 \le i \le n$，若 $a_i = x$，则 $a_i \leftarrow 0$）。

你希望使用最少的操作次数，使得数列变成一个非降的数列，即 $a_1 \le a_2 \le a_3 \le \ldots \le a_n$。

求：使数列变成一个非降序列所需的最少操作次数？

输入格式

第一行，一个整数 $n(1 \le n \le 2 \cdot 10^5)$，表示数列大小。

第二行，$n$ 个整数 $a_1, a_2, \ldots, a_n(1 \le a_i \le n)$。

输出格式

输出一个整数，表示是数列 $a$ 变成一个非降序列所需的最少操作次数。

input1

3
3 3 2

output1

1

input2

4
1 3 1 3

output2

2

说明/提示

样例解释

样例1：选择 $x = 3$，操作后数列变为 $[0, 0, 2]$；

样例2：第一次操作选择 $x = 1$，第二次操作选择 $x = 3$，数列变为 $[0, 0, 0, 0]$。

数据规模与约定

• 对于 $20\%$ 的数据，$n \le 20$
• 对于 $50\%$ 的数据，$n \le 2000$
• 对于 $100\%$ 的数据，$1 \le n \le 2 \cdot 10^5; 1 \le a_i \le n$