小苯的好数组

题目描述

大白熊给了小苯一个长度为 nnn 的数组 aaa，这次他希望小苯从数组中选择一个子序列（下方备注有定义解释），满足这个子序列构成的数组是一个“好数组”。

大白熊定义好数组是：如果一个数组按升序排序后和原来不完全相同，则其是一个好数组。例如 [3,2,2][3,2,2][3,2,2] 升序排序后是 [2,2,3][2, 2, 3][2,2,3]，和原来不完全相同，因此是一个好数组，而 [1,2,2][1,2,2][1,2,2] 不是一个好数组。

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

输入描述:

输入包含两行。
第一行一个正整数 n (1≤n≤2×105)n \ (1 \leq n \leq 2 \times 10^5)n (1≤n≤2×105)，表示数组 aaa 的长度。
第二行 nnn 的正整数 ai(1≤ai≤109)a_i (1\leq a_i \leq 10^9)ai​(1≤ai​≤109)，表示数组 aaa 的元素。

输出描述:

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

示例1

输入

复制1 1

1
1

输出

复制0

0

说明

只能选择 111，但 [1][1][1] 这个数组满足单调不降，因此无法选择数字，答案为 000。

备注:

子序列：一个数组删除一些数字后（也可以不删），剩余的数字按其原来的顺序构成的序列。
例如：[2,3][2,3][2,3] 是 [1,2,4,3][1,2,4,3][1,2,4,3] 的一个子序列，同时 [1,2,4,3][1,2,4,3][1,2,4,3] 也是自己的子序列，但 [3,2][3,2][3,2] 并不是 [1,2,4,3][1,2,4,3][1,2,4,3] 的子序列。
空数组是任何数组的子序列。