该比赛已结束，您无法在比赛模式下递交该题目。您可以点击“在题库中打开”以普通模式查看和递交本题。

小田的好数组

本题需要使用文件输入输出，文件名为hsz.in、hsz.out。

题目描述

小田得到了一个长度为 $n$ 的数组 $a$，他希望从数组中选择一个子序列，并使得这个子序列构成的数组是一个“好数组”。

对于“好数组”的定义是：如果一个数组按升序排序后和原来的不完全相同，则是一个好数组。例如 $[3, 2, 2]$ 升序排列后是 $[2, 2, 3]$，和原来不完全相同，因此是一个好数组，而 $[1, 2, 2]$ 不是一个好数组。

小田想知道，如果想要使得选择的子序列构成一个“好数组”，最长可以选择多长的子序列？

说明：子序列指一个数组删除一个数字后（也可以不删），剩余的数字按其原来的顺序构成的序列。

例如：$[2, 3]$ 是 $[1, 2, 4, 3]$ 的一个子序列，$[1, 2, 4, 3]$ 也是，但 $[3, 2]$ 不是。

输入描述

输入包含两行。

第一行一个正整数 $n$，表示数组 $a$ 的长度。

第二行 $n$ 的正整数 $a_{i}$，表示数组 $a$ 的元素。

输出描述

输出包含一行一个整数，表示可以构成“好数组”的最长子序列的长度。

输入输出样例

输入 #1

1
1

输出 #1

0

输入 #2

2
2 1

输出 #2

2

说明/提示

【样例 1 解释】

只能选择 $1$，但 $[1]$ 这个数组排序后还是 $[1]$，无法满足不完全相同的条件。

【样例 2 解释】

选择 $[2, 1]$，排序后是 $[1, 2]$，满足不完全相同的要求。

【数据范围】

对于 $10 \%$ 的数据，有：$1 \le n \le 2$ 。

对于另外 $10 \%$ 的数据，有：所有 $a_i$ 完全相等。

对于所有测试数据，有：$1 \le n \le 2 \times 10^{5}, 1 \le a_{i} \le 10^9$ 。